Palindrome Permutation

Easy · Bit Manipulation · Explanation and code example

Using Set

How it works

A set provides an elegant way to track characters with odd frequencies. When we see a character for the first time, we add it to the set. When we see it again, we remove it. Characters that appear an even number of times cancel out and leave the set. Only characters with odd frequencies remain.

At the end, if the set has at most one element, a palindrome permutation is possible.

Steps

Initialize an empty set.
For each character in the string:
- If the character is already in the set, remove it.
- Otherwise, add it to the set.
Return true if the set contains at most one character.

Complexity

Time complexity: O(n)
Space complexity: O(1) If the we assume the input contains only ASCII characters.
- O(k) If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. O(n) in the worst case (if all characters are unique)

Where n is the size of the input string s and where k is the number of unique characters in s

Things to watch for

Forgetting That One Odd Count Is Allowed

A common mistake is checking if all character counts are even. For odd-length palindromes, exactly one character can have an odd count (the middle character). The condition should be oddCount <= 1, not oddCount == 0.

Confusing Palindrome With Palindrome Permutation

Some developers attempt to check if the string itself is a palindrome rather than if any permutation can form one. The problem asks about rearranging characters, so only character frequencies matter, not their positions in the original string.

2. Using HashMap

Intuition

Instead of iterating through all possible ASCII characters, we can use a hash map to only track characters that actually appear in the string. This is more efficient when the string uses a small subset of the character set.

We count the frequency of each character, then check how many have odd counts. The palindrome condition remains the same: at most one odd frequency.

Algorithm

Use a hash map to store the frequency of each character in the string.
Iterate through the string once, incrementing counts for each character.
Count how many characters have odd frequencies.
Return true if the odd count is at most 1.

Time & Space Complexity

Time complexity: O(n)
- O(n + k) If we generalize the solution to handle any Unicode character. In the worst case (k = n), this becomes O(n).
Space complexity: O(1) If the we assume the input contains only ASCII characters.
- O(k) If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. O(n) in the worst case (if all characters are unique).

Where n is the size of the input string s and where k is the number of unique characters in s

Common Pitfalls

Forgetting That One Odd Count Is Allowed

Confusing Palindrome With Palindrome Permutation

3. Using Array

Intuition

Since we know the input contains only ASCII characters (128 possible values), we can replace the hash map with a fixed-size array. Array access is faster than hash map lookups, and we avoid the overhead of hashing.

The logic is identical to the hash map approach, but we use the character's ASCII value as the array index.

Algorithm

Create an array of size 128 to store character frequencies.
Iterate through the string, using each character's ASCII value as an index.
Increment the count at each index.
Count how many array positions have odd values.
Return true if at most one position has an odd count.

Time & Space Complexity

Time complexity: O(n)
Space complexity: O(1) If the we assume the input contains only ASCII characters.
- O(k) If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. O(n) in the worst case (if all characters are unique).

Where n is the size of the input string s and where k is the number of unique characters in s

Common Pitfalls

Forgetting That One Odd Count Is Allowed

Confusing Palindrome With Palindrome Permutation

4. Single Pass

Intuition

We can optimize further by tracking the odd count dynamically as we process each character. When a character's frequency becomes even, we decrement the odd count. When it becomes odd, we increment. This way, we know the final answer immediately after one pass without needing a second loop.

Algorithm

Create an array of size 128 for character frequencies and initialize an odd counter to 0.
For each character in the string:
- Increment its count in the array.
- If the new count is even, decrement the odd counter.
- If the new count is odd, increment the odd counter.
Return true if the odd counter is at most 1.

Time & Space Complexity

Time complexity: O(n)
Space complexity: O(1) If the we assume the input contains only ASCII characters.
- O(k) If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. O(n) in the worst case (if all characters are unique).

Where n is the size of the input string s and where k is the number of unique characters in s

Common Pitfalls

Forgetting That One Odd Count Is Allowed

Confusing Palindrome With Palindrome Permutation

5. Using Set

Intuition

At the end, if the set has at most one element, a palindrome permutation is possible.

Algorithm

Initialize an empty set.
For each character in the string:
- If the character is already in the set, remove it.
- Otherwise, add it to the set.
Return true if the set contains at most one character.

Time & Space Complexity

Time complexity: O(n)
Space complexity: O(1) If the we assume the input contains only ASCII characters.
- O(k) If the implementation is modiifed to handle Unicode characters, the space complexity would depend on the number of unique characters in the string. O(n) in the worst case (if all characters are unique)

Where n is the size of the input string s and where k is the number of unique characters in s

Common Pitfalls

Forgetting That One Odd Count Is Allowed

Confusing Palindrome With Palindrome Permutation

Python code example

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        chars = set()
        for c in s:
            if c in chars:
                chars.remove(c)
            else:
                chars.add(c)
        return len(chars) <= 1

C++ code example

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_set<char> char_set;
        for (char c : s) {
            if (char_set.find(c) != char_set.end())
                char_set.erase(c);
            else
                char_set.insert(c);
        }
        return char_set.size() <= 1;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations