Question 13.1 - Test for palindromic permutations uses a HashMap to count occurrences of characters in a String. If we have a maximum of one character with an odd count, the test passes:
public static boolean canFormPalindrome(String s) {
Map<Character, Integer> charFrequencies = new HashMap<>();
// Compute the frequency of each char in s.
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!charFrequencies.containsKey(c)) {
charFrequencies.put(c, 1);
} else {
charFrequencies.put(c, charFrequencies.get(c) + 1);
}
}
// A string can be permuted as a palindrome if and only if the number of
// chars whose frequencies is odd is at most 1.
int oddCount = 0;
for (Map.Entry<Character, Integer> p : charFrequencies.entrySet()) {
if ((p.getValue() % 2) != 0 && ++oddCount > 1) {
return false;
}
}
return true;
}
Wouldn’t it be easier to simply use a HashSet and to add/remove characters as we encounter them as such:
public static boolean canFormPalindrome(String s) {
HashSet<Character> charSet = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (charSet.contains(c)) {
charSet.remove(c);
} else {
charSet.add(c);
}
}
return charSet.size() <= 1;
}
If, in the end, we have more than one item in the set, this means we have more than one character with an odd count, i.e. the output should be identical to the solution above. Is there a time complexity issue due to the n remove/add calls?