266: Palindrome Permutation

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

For example,

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

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);

            if (map.containsKey(letter)) {
                int count = map.get(letter) + 1;
                map.put(letter, count);
            } else {
                map.put(letter, 1);
            }
        }

        int tolerance = 0;
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();

            if ((int) pair.getValue() % 2 != 0) {
                tolerance++;
            }
        }

        if (s.length() % 2 == 0) {
            return tolerance == 0;
        } else {
            return tolerance == 1;
        }
    }
}

The basic idea is using HashSet to find the number of single characters, which should be at most 1.

public boolean canPermutePalindrome(String s) {
    Set<Character>set = new HashSet<Character>();
    for (char c : s.toCharArray())  
        if (set.contains(c)) set.remove(c);// If char already exists in set, then remove it from set
        else set.add(c);// If char doesn't exists in set, then add it to set
    return set.size() <= 1;
}