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.

Solution:

Go through the string character by character. Use a HashMap to store the character we meet.

If we see a new character, we set the value in the HashMap to 1. If we see it again, we set the value to 0.

Therefore, if any number appeared once, its value in the HashMap is 1. If it appeared in pairs, its value in the HashMap is 0.

Hence, we check sum of values in the HashMap. If sum is 0 or 1, we know the string can be reconstructed to a palindrome.

The time complexity is O(n) and the space complexity is also O(n).



Code:

public class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] check = new int[256];
        for (int i = 0; i < s.length(); i++) {
            if (check[s.charAt(i)] == 0) {
                check[s.charAt(i)]++;
            }
            else {
                check[s.charAt(i)]--;
            }
        }
        int sum = 0;
        for (int i = 0; i < check.length; i++) {
            sum += check[i];
        }
        return sum == 0 || sum == 1;
    }
}