Give an algorithm to decide whether a given string or ANY of its permutations is a Palindrome. There is an O(n) algorithm for this problem!

permutationPalindrome.java

/**
 * Decide whether a given string or ANY
 * of its permutations is a Palindrome.
 *
 * The given solution works in O(n). Building the parity map
 * takes n steps, iterating through the map takes
 * not more than n steps (size of the alphabet).
 * Space consumption: Map with the size of the alphabet. (constant)
 * @param str
 * @return
 */
public static boolean permutPalin(String str){
    char[] chars = str.toCharArray();

    Map<Character, Boolean> parityMap = new HashMap<>();

    for(int i = 0; i < chars.length; i++){
        if(parityMap.get(chars[i]) == null){
            parityMap.put(chars[i], false);
        }
        boolean val = parityMap.get(chars[i]);
        parityMap.put(chars[i], !val);
    }

    int count = 0;
    for(Map.Entry e: parityMap.entrySet()){
        if((Boolean) e.getValue()){
            count++;
        }
        if(count > 1) return false;
    }

    return true;
}