266-palindrome-permutation

Question

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

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

Example:

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

Thought Process

1. Hash Table - Two passes
   1. Use map to store the frequency of character, if we have seen odd frequency more than once, we can't make a permutation that is palindrom
   2. Time complexity O(n)
   3. Space complexity O(n)
2. Hash Table - One pass

Solution

class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s.length() <= 1) return true;
        int[] map = new int[128];
        char[] chars = s.toCharArray();
        for (char c : chars) map[c]++;
        boolean oddSeen = false;
        for (char a = 0; a < 128; a++) {
            if (map[a] % 2 == 1) {
                if (oddSeen) return false;
                oddSeen = true;
            }
        }
        return true;
    }
}

class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s.length() <= 1) return true;
        int[] map = new int[128];
        int oddCnt = 0;
        for (char c : s.toCharArray()) {
            map[c]++;
            if (map[c] % 2 == 1) oddCnt++;
            else oddCnt--;
        }
        return oddCnt <= 1 ? true : false;
    }
}

Additional