Given a string, determine if a permutation of the string could form a palindrome.

For example,
“code” -> False, “aab” -> True, “carerac” -> True.

One pass without counters.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public boolean canPermutePalindrome(String s) {
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++){
            if (!set.add(s.charAt(i))){
                set.remove(s.charAt(i));
            }
        }
        
        return set.size() <= 1;
    }
}

Using a Bitset

1
2
3
4
5
6
public boolean canPermutePalindrome(String s) {
    BitSet bs = new BitSet();
    for (byte b : s.getBytes())
        bs.flip(b);
    return bs.cardinality() < 2;
}