LeetCode 266 - Palindrome Permutation

LeetCode Problem 266

Difficulty: 🟢 Easy
Topics: Hash Table, String, Bit Manipulation

Solution

Problem Understanding

The problem asks whether the characters of a given string can be rearranged to form a palindrome. A palindrome is a string that reads the same forward and backward. Examples include "racecar", "abba", and "a".

The important detail is that we are not asked to actually generate the palindrome. We only need to determine whether at least one permutation of the input string could form one.

The input is a string s containing only lowercase English letters. The output is a boolean value:

• Return true if some rearrangement of the characters forms a palindrome.
• Return false otherwise.

The constraints tell us that the string length can be as large as 5000 characters. This size is large enough that generating all permutations is completely infeasible. Since the alphabet is limited to lowercase English letters, frequency counting becomes a very natural approach.

To understand the key property of palindromes, consider how characters are arranged inside one:

• In an even-length palindrome, every character must appear an even number of times because characters mirror each other around the center.
• In an odd-length palindrome, exactly one character may appear an odd number of times, because the middle character does not need a matching pair.

This observation leads directly to the optimal solution.

Several edge cases are important:

• A single-character string should always return true.
• Strings where every character count is even should return true.
• Strings with more than one odd frequency should return false.
• The input only contains lowercase letters, so we do not need to handle uppercase normalization or special characters.

Approaches

Brute Force Approach

A brute-force solution would generate every possible permutation of the string and check whether any permutation is a palindrome.

To do this, we would:

1. Generate all permutations of the string.
2. For each permutation, check whether it reads the same forward and backward.
3. Return true if at least one palindrome exists.

This approach is correct because it exhaustively checks every possible arrangement of the characters. If a palindrome permutation exists, the algorithm will eventually find it.

However, this method is far too slow. A string of length n has n! permutations. Even for relatively small values of n, factorial growth becomes enormous. Since the constraint allows up to 5000 characters, brute force is completely impractical.

Optimal Approach

The key insight is that we do not care about the actual arrangement of characters. We only care about their frequencies.

A palindrome has a strict structural property:

• Characters on the left side must match characters on the right side.
• Therefore, most characters must appear an even number of times.
• At most one character may have an odd frequency.

So the problem reduces to counting character frequencies and checking how many characters have odd counts.

If the number of odd-frequency characters is:

• 0, the string can form an even-length palindrome.
• 1, the string can form an odd-length palindrome.
• Greater than 1, forming a palindrome is impossible.

This transforms the problem from factorial complexity into a simple linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n!)	Generates all permutations and checks each one
Optimal	O(n)	O(1)	Counts character frequencies and checks odd counts

Algorithm Walkthrough

Optimal Frequency Counting Algorithm

1. Create a hash map or frequency array to count how many times each character appears in the string.

We need frequency information because palindrome validity depends entirely on character counts. Since the input only contains lowercase English letters, we could use either a hash map or a fixed-size array of length 26. 2. Traverse the string character by character.

For each character, increment its frequency count. After this step, we know exactly how many times every letter appears. 3. Count how many characters have odd frequencies.

A character with an odd frequency cannot be perfectly mirrored across the palindrome unless it occupies the center position. 4. Check the number of odd-frequency characters.

• If more than one character has an odd count, return false.
• Otherwise, return true.

5. Finish the computation.

The result directly follows from the mathematical property of palindromes.

Why it works

The algorithm works because every palindrome requires mirrored character pairs. Even-frequency characters can always be split evenly between the left and right halves. An odd-frequency character leaves one extra copy unmatched, which is only valid for the single center position in an odd-length palindrome. Therefore, a string can form a palindrome if and only if at most one character has an odd frequency.

Python Solution

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        frequency = {}

        for char in s:
            frequency[char] = frequency.get(char, 0) + 1

        odd_count = 0

        for count in frequency.values():
            if count % 2 == 1:
                odd_count += 1

            if odd_count > 1:
                return False

        return True

The implementation begins by creating a dictionary called frequency. This dictionary stores how many times each character appears in the string.

The first loop iterates through every character in the input string and updates its count. Using frequency.get(char, 0) allows us to safely initialize missing characters to zero.

Next, the algorithm iterates through all frequency values. For each count, it checks whether the value is odd using the modulus operator %.

Whenever an odd count is found, odd_count increases by one. If more than one odd frequency exists, the function immediately returns False because a palindrome permutation is impossible.

If the loop completes without exceeding one odd frequency, the function returns True.

Go Solution

func canPermutePalindrome(s string) bool {
    frequency := make(map[rune]int)

    for _, char := range s {
        frequency[char]++
    }

    oddCount := 0

    for _, count := range frequency {
        if count%2 == 1 {
            oddCount++
        }

        if oddCount > 1 {
            return false
        }
    }

    return true
}

The Go implementation follows the same logic as the Python solution. A map[rune]int is used to store character frequencies.

Go strings are UTF-8 encoded, so iterating with for _, char := range s produces runes rather than raw bytes. Although this problem only contains lowercase English letters, using runes is still idiomatic and safe.

Unlike Python dictionaries, Go maps automatically return the zero value for missing keys, so incrementing frequencies is straightforward with frequency[char]++.

There are no concerns about integer overflow because the maximum string length is only 5000.

Worked Examples

Example 1

Input: s = "code"

Step-by-step trace

Character	Frequency Map
c	{c: 1}
o	{c: 1, o: 1}
d	{c: 1, o: 1, d: 1}
e	{c: 1, o: 1, d: 1, e: 1}

Now count odd frequencies:

Character	Count	Odd?
c	1	Yes
o	1	Yes
d	1	Yes
e	1	Yes

There are 4 odd counts.

Since more than one odd frequency exists, the answer is false.

Example 2

Input: s = "aab"

Step-by-step trace

Character	Frequency Map
a	{a: 1}
a	{a: 2}
b	{a: 2, b: 1}

Now count odd frequencies:

Character	Count	Odd?
a	2	No
b	1	Yes

There is exactly 1 odd count.

A palindrome permutation exists, such as "aba".

The answer is true.

Example 3

Input: s = "carerac"

Step-by-step trace

Character	Frequency Map
c	{c: 1}
a	{c: 1, a: 1}
r	{c: 1, a: 1, r: 1}
e	{c: 1, a: 1, r: 1, e: 1}
r	{c: 1, a: 1, r: 2, e: 1}
a	{c: 1, a: 2, r: 2, e: 1}
c	{c: 2, a: 2, r: 2, e: 1}

Now count odd frequencies:

Character	Count	Odd?
c	2	No
a	2	No
r	2	No
e	1	Yes

Only one odd count exists.

A palindrome permutation exists, such as "racecar".

The answer is true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(1)	At most 26 lowercase letters are stored

The algorithm performs a single pass through the string to count frequencies and another pass through the frequency table to count odd occurrences. Since the alphabet size is fixed at 26 lowercase letters, the auxiliary space remains constant regardless of input size.

Test Cases

solution = Solution()

assert solution.canPermutePalindrome("code") == False  # multiple odd counts
assert solution.canPermutePalindrome("aab") == True  # one odd count
assert solution.canPermutePalindrome("carerac") == True  # valid palindrome permutation

assert solution.canPermutePalindrome("a") == True  # single character
assert solution.canPermutePalindrome("aa") == True  # all even counts
assert solution.canPermutePalindrome("ab") == False  # two odd counts

assert solution.canPermutePalindrome("aaa") == True  # one odd count
assert solution.canPermutePalindrome("aabb") == True  # even-length palindrome possible
assert solution.canPermutePalindrome("aabbc") == True  # one center character

assert solution.canPermutePalindrome("abc") == False  # all odd counts
assert solution.canPermutePalindrome("aaabbb") == False  # two odd counts

assert solution.canPermutePalindrome("ccccddddd") == True  # one odd frequency
assert solution.canPermutePalindrome("abcdefghijklmnopqrstuvwxyz") == False  # many odd counts

Test	Why
"code"	Verifies multiple odd frequencies fail
"aab"	Verifies one odd frequency succeeds
"carerac"	Confirms valid rearrangement exists
"a"	Smallest valid input
"aa"	Simple even palindrome case
"ab"	Minimal failing case
"aaa"	Odd-length palindrome
"aabb"	All characters paired evenly
"aabbc"	One center character allowed
"abc"	Every character odd
"aaabbb"	Multiple odd frequencies
"ccccddddd"	Large repeated counts
"abcdefghijklmnopqrstuvwxyz"	Stress case with many unique letters

Edge Cases

Single-character strings

A string containing only one character is always a palindrome because it reads the same forward and backward. A naive implementation might incorrectly assume at least one pair is required. This implementation handles the case correctly because there is exactly one odd frequency, which is allowed.

Strings with all unique characters

Inputs like "abc" are important because every character appears once. That means multiple odd frequencies exist simultaneously. The implementation correctly detects this by counting odd occurrences and returning False once the count exceeds one.

Strings with all even frequencies

Inputs like "aabbcc" represent perfect pairing cases. Every character can be mirrored across the center of the palindrome. The implementation correctly returns True because the odd-frequency count remains zero throughout the check.

Odd-length valid palindromes

Cases like "aabbc" are subtle because one character is allowed to remain unmatched. Some incorrect implementations mistakenly require all counts to be even. This solution explicitly allows exactly one odd frequency, ensuring such inputs are handled properly.