Link

Easy Hash Table

Apple

Microsoft

2020-05-24

266. Palindrome Permutation

Similar Question: LeetCode Question 1457

Question:

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:

Using hash table to record the frequency of each character, if there are more than one character have the odd frequency, return false. Otherwise, it has a permutation which can form a palindrome.

class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) return false;
        int[] hash = new int[128];
        int counter = 0;
        for(char c: s.toCharArray()) {
            hash[c]++;
        }
        for (int i : hash) {
            if (i % 2 == 1) {
                counter++;
            }
            if (counter > 1) {
                return false;
            }
        }
        return true;
    }
}