LeetCode 266: Palindrome Permutation

Problem Restatement

We are given a string s.

Return True if some permutation of s can form a palindrome.

Return False otherwise.

A palindrome reads the same forward and backward.

For example:

"aba"
"racecar"
"abba"

The order of characters in s can be rearranged. We only need to know whether at least one palindrome arrangement exists.

The constraints are 1 <= s.length <= 5000, and s contains only lowercase English letters. The examples are "code" -> false, "aab" -> true, and "carerac" -> true.

Input and Output

Example function shape:

def canPermutePalindrome(s: str) -> bool:
    ...

Examples

Example 1:

s = "code"

Character counts:

There are four characters with odd counts.

A palindrome can have at most one odd-count character.

Answer:

False

Example 2:

s = "aab"

Character counts:

Only b has an odd count.

We can arrange the string as:

"aba"

Answer:

True

Example 3:

s = "carerac"

Character counts:

Only e has an odd count.

A valid palindrome arrangement exists.

Answer:

True

First Thought: Generate Permutations

A direct approach is to generate every permutation of s, then check whether any permutation is a palindrome.

For "aab", possible permutations include:

"aab"
"aba"
"baa"

Since "aba" is a palindrome, the answer is True.

This approach is correct, but it is far too expensive.

Problem With Brute Force

A string of length n can have up to:

n!

permutations.

Even for moderate n, this becomes impossible.

We need a way to decide whether a palindrome can exist without constructing the palindrome.

Key Insight

A palindrome mirrors characters around its center.

For an even-length palindrome:

"abba"

every character appears an even number of times.

For an odd-length palindrome:

"abcba"

exactly one character may appear an odd number of times. That character goes in the middle.

So the rule is:

A string can be permuted into a palindrome if and only if at most one character has an odd frequency.

Algorithm

1. Count how many times each character appears.
2. Count how many characters have odd frequency.
3. Return True if the odd count is at most 1.
4. Otherwise return False.

Walkthrough

Use:

s = "carerac"

Count characters:

c -> 2
a -> 2
r -> 2
e -> 1

Odd-count characters:

e

There is only one odd-count character.

So a palindrome permutation exists.

Return:

True

Use:

s = "code"

Count characters:

c -> 1
o -> 1
d -> 1
e -> 1

There are four odd-count characters.

A palindrome cannot have four middle characters.

Return:

False

Correctness

In any palindrome, every character on the left side must be matched by the same character on the right side.

Therefore, every character must appear an even number of times, except possibly one character placed in the center of an odd-length palindrome.

So if more than one character has an odd count, no palindrome permutation can exist.

If zero or one character has an odd count, we can place half of each character on the left side, mirror those characters on the right side, and place the one odd-count character in the center when it exists.

Therefore the algorithm returns True exactly when a palindrome permutation exists.

Complexity

Implementation

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        freq = [0] * 26

        for ch in s:
            freq[ord(ch) - ord("a")] += 1

        odd_count = 0

        for count in freq:
            if count % 2 == 1:
                odd_count += 1

                if odd_count > 1:
                    return False

        return True

Code Explanation

We use an array of size 26:

freq = [0] * 26

Each lowercase letter maps to an index:

ord(ch) - ord("a")

Then we count frequencies:

freq[ord(ch) - ord("a")] += 1

After counting, we count how many frequencies are odd:

if count % 2 == 1:
    odd_count += 1

If more than one odd count appears:

if odd_count > 1:
    return False

At the end, zero or one odd count means a palindrome permutation is possible.

Alternative: Toggle a Set

Another clean method stores characters with odd frequency.

When a character appears once, add it.

When it appears again, remove it.

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        odd = set()

        for ch in s:
            if ch in odd:
                odd.remove(ch)
            else:
                odd.add(ch)

        return len(odd) <= 1

At the end, odd contains exactly the characters with odd frequency.

Testing

def run_tests():
    s = Solution()

    assert s.canPermutePalindrome("code") is False
    assert s.canPermutePalindrome("aab") is True
    assert s.canPermutePalindrome("carerac") is True
    assert s.canPermutePalindrome("a") is True
    assert s.canPermutePalindrome("aa") is True
    assert s.canPermutePalindrome("ab") is False
    assert s.canPermutePalindrome("aabb") is True
    assert s.canPermutePalindrome("abcabc") is True
    assert s.canPermutePalindrome("abc") is False

    print("all tests passed")

run_tests()

Test meaning: