LeetCode 266. Palindrome Permutation

Question

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

Input: s = "code"
Output: false

Example 2:

Input: s = "aab"
Output: true

Example 3:

Input: s = "carerac"
Output: true

Constraints:

• 1 <= s.length <= 5000
• s consists of only lowercase English letters.

Source: https://leetcode.com/problems/palindrome-permutation/

Solution

public boolean canPermutePalindrome(String s) {
    Map<Character, Integer> charCount = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    int oddCount = 0;
    for (int count : charCount.values()) {
        if (count % 2 == 1) {
            oddCount++;
        }
    }
    // at most one character can appear odd times
    return oddCount == 0 || oddCount == 1;
}

public boolean canPermutePalindrome2(String s) {
    Set<Character> charSet = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (charSet.contains(c)) {
            charSet.remove(c);
        } else {
            charSet.add(c);
        }
    }
    return charSet.size() == 0 || charSet.size() == 1;
}