266. Palindrome Permutation

Description

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

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

Solution

HashMap, O(n), S(n)

class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null) {
            return false;
        }
        
        Map<Character, Integer> freq = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char c = s.charAt(i);
            freq.put(c, 1 + freq.getOrDefault(c, 0));
        }
        
        int oddCount = 0;
        for (int count : freq.values()) {
            if (count % 2 > 0) {
                ++oddCount;
            }
        }
        
        return (len % 2 == 0 && oddCount == 0) 
            || (len % 2 > 0 && oddCount == 1);
    }
}