Palindrome Permutation

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

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?
2. Count the frequency of each character.
3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Solution1: HashMap
key存字母， value存字母出现的次数。如果每个字母都出现偶数次，true。如果只有一个字母出现奇数次，true。其余情况返回false。
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            }
        }
        
        int oddCount = 0;
        for (Map.Entry entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                oddCount += 1;
            }
        }
        
        if (oddCount > 1) {
            return false;
        }
        
        return true;
    }
}

Solution2: HashSet
如果set中存在这个字母，从set中将其删除； 如果set中不存在，把字幕放进set里。
loop好之后，查看set的大小，如果大于1，说明有不止1个字母出现奇数次，不可以组成palindrome，返回false。
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashSet set = new HashSet();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                set.remove(s.charAt(i));
            } else {
                set.add(s.charAt(i));
            }
        }
        
        return set.size() <= 1;
    }
}