266.md

266. Palindrome Permutation

Description

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

For example,

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

Thinking Process

1. A palindrome can have at most 1 character that appears odd number of times
2. A straightforward solution is to count the number of occurance of each character in s, if there are more than 1 character in s appear odd number of times, there would be no solution to the problem
3. An optimization to the problem can be carried out by using a hashset.
   1. Scan through s, if the character is in the set, remove it from the set; otherwise add it to the set
   2. The operation in step 3.1 ensures that only character appears odd number of times will remain in the set.
   3. Return if the set has a size smaller than 2

Code

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

Complexity

1. Time complexity is O(n) as the string is scanned exactly once
2. Space complexity is upto O(n) as the size of the set can be as large as the length of the string (s has no duplicate characters)