1.4 Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rea rrangement of letters. The palindrome does not need to be limited to just dictionary words.
EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat". "atco cta". etc.)
Just check that no more than one character appears an odd number of times. Because if there is one, then it must be in the middle of the palindrome. So we can't have two of them.
For even Palindrome, all char number must be even
For odd palindrome, all char number must be even except one odd.
public boolean canPermutePalindrome(String s) {
Set<Character> set=new HashSet<Character>();
for(int i=0; i<s.length(); i++){
if (!set.contains(s.charAt(i)))
set.add(s.charAt(i));
else
set.remove(s.charAt(i));
}
return set.size()==0 || set.size()==1;
}
Or reduce the space usage by using a bit vector
public boolean canPermutePalindrome(String s) {
BitSet bs = new BitSet();
for (byte b : s.getBytes())
bs.flip(b);
return bs.cardinality() < 2;
}
