LeetCode 266: Palindrome Permutation Solution in Python – A Step-by-Step Guide

What Is LeetCode 266: Palindrome Permutation?

In LeetCode 266: Palindrome Permutation, you’re given a string s, and your task is to determine if it’s possible to rearrange the string into a palindrome. A palindrome has a key property: it can have at most one character with an odd frequency, as all others must pair up symmetrically. For example, "code" can’t form a palindrome (too many odd frequencies), but "car" can ( rearranged as "rac"). You return True if a palindromic permutation exists, False otherwise.

Problem Statement

• Input: A string s.
• Output: A boolean—True if s can be rearranged into a palindrome, False otherwise.
• Rules:
• A palindrome permutation has at most one character with an odd count.
• All other characters must have even counts.

Constraints

• 1 <= s.length <= 5000
• s consists of lowercase English letters.

Examples

• Input: s = "code"
• Output: False
• Why: Frequencies: c:1, o:1, d:1, e:1 (four odd counts).
• Input: s = "aab"
• Output: True
• Why: Frequencies: a:2, b:1 (one odd count), can be "aba".
• Input: s = "carerac"
• Output: True
• Why: Frequencies: c:2, a:2, r:2, e:1 (one odd), can be "racecar".

Understanding the Problem: Checking Palindromic Potential

To solve LeetCode 266: Palindrome Permutation in Python, we need to check if a string can be rearranged into a palindrome by analyzing character frequencies. A palindrome permutation requires at most one character to have an odd count (the middle character in odd-length palindromes), with all others even. A naive approach—generating all permutations and checking each—would take O(n!) time, which is impractical for 5000 characters. Instead, we’ll use frequency counting:

• Best Solution (Hash Map): O(n) time, O(k) space—counts characters efficiently.
• Alternative Solution (Bit Vector): O(n) time, O(1) space—uses bits for compactness.

Let’s dive into the Best Solution—hash map with frequency counting—and break it down step-by-step.

Best Solution: Hash Map with Character Frequency Counting

Why This Is the Best Solution

The hash map approach is the top choice because it’s both efficient—O(n) time and O(k) space (where k is the character set size)—and intuitive, using a dictionary to count character frequencies and check for odd counts. It’s straightforward and readable, making it ideal for most use cases. It’s like tallying up votes for each letter, then seeing if more than one got an odd number—simple and fast!

How It Works

Here’s the strategy:

• Step 1: Count Frequencies:
• Use a hash map to count occurrences of each character in s.
• Step 2: Count Odd Frequencies:
• Iterate through the map, count how many characters have odd frequencies.
• Step 3: Check Condition:
• Return True if odd count ≤ 1, False otherwise.

Step-by-Step Example

Example: s = "carerac"

• Step 1: Count Frequencies:
• freq = {'c': 2, 'a': 2, 'r': 2, 'e': 1}.
• Step 2: Count Odd Frequencies:
• 'c': 2 (even), 'a': 2 (even), 'r': 2 (even), 'e': 1 (odd).
• Odd count = 1.
• Step 3: Check:
• Odd count = 1 ≤ 1, return True.
• Result: True (can be "racecar").

Example: s = "code"

• Step 1: Count Frequencies:
• freq = {'c': 1, 'o': 1, 'd': 1, 'e': 1}.
• Step 2: Count Odd Frequencies:
• All 1 (odd), odd count = 4.
• Step 3: Check:
• Odd count = 4 > 1, return False.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # Step 1: Initialize frequency map
        freq = {}

        # Step 2: Count frequencies
        for char in s:
            freq[char] = freq.get(char, 0) + 1

        # Step 3: Count odd frequencies
        odd_count = 0
        for count in freq.values():
            if count % 2 != 0:
                odd_count += 1
            if odd_count > 1:  # Early exit
                return False

        # Step 4: Return result
        return True

• Line 4: Initialize empty hash map.
• Line 7-8: Count each character’s frequency.
• Line 11-15: Count odd frequencies:
• Line 13-14: Increment if odd, early exit if > 1.
• Line 18: Return True if ≤ 1 odd count.
• Time Complexity: O(n)—single pass through string.
• Space Complexity: O(k)—k is character set size (26 here).

This is a frequency-counting champ!

Alternative Solution: Bit Vector Approach

Why an Alternative Approach?

The bit vector approach offers a space-optimized alternative—O(n) time, O(1) space—using a single integer as a bit mask to track odd/even frequencies, leveraging bitwise operations. It’s ideal when minimizing space is critical, though less readable. It’s like using a secret code to tally odds with bits—compact and clever!

How It Works

• Step 1: Use a bit vector (integer) where each bit represents a character’s parity (0 for even, 1 for odd).
• Step 2: Toggle bits for each character using XOR.
• Step 3: Check if result has at most one 1-bit (odd count).

Step-by-Step Example

Example: s = "carerac"

• Step 1: Initialize Bit Vector:
• bit_vector = 0.
• Step 2: Toggle Bits (using 'a' = 0, 'c' = 2, 'r' = 17, 'e' = 4):
• 'c' (2): bit_vector ^= 1 << 2 → 4.
• 'a' (0): 4 ^= 1 << 0 → 5.
• 'r' (17): 5 ^= 1 << 17 → 131077.
• 'e' (4): 131077 ^= 1 << 4 → 131061.
• 'r' (17): 131061 ^= 1 << 17 → 13.
• 'a' (0): 13 ^= 1 << 0 → 12.
• 'c' (2): 12 ^= 1 << 2 → 8 (only 'e' bit remains).
• Step 3: Check:
• bit_vector = 8 (binary 1000), one 1-bit → True.
• Result: True.

Code for Bit Vector Approach

Copy codeclass Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # Step 1: Initialize bit vector
        bit_vector = 0

        # Step 2: Toggle bits for each character
        for char in s:
            bit_vector ^= 1 << (ord(char) - ord('a'))

        # Step 3: Check if at most one bit is 1
        # bit_vector & (bit_vector - 1) is 0 if ≤ 1 bit set
        return bit_vector == 0 or (bit_vector & (bit_vector - 1)) == 0

• Line 4: Start with 0.
• Line 7-8: XOR to toggle bit for each char.
• Line 11: Check if 0 or one 1-bit (trick: n & (n-1) clears least significant 1).
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—single integer.

It’s a bit-twiddling marvel!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n) time, O(k) space, readable and intuitive.
• Cons: More space than bit vector.
• Bit Vector (Alternative):
• Pros: O(n) time, O(1) space, ultra-compact.
• Cons: Less readable, assumes small charset.

Hash map wins for clarity and generality.

Additional Examples and Edge Cases

• "a": True (one odd).
• "aa": True (no odd).
• "abcd": False (four odd).

Both handle these perfectly.

Complexity Breakdown

• Hash Map: Time O(n), Space O(k).
• Bit Vector: Time O(n), Space O(1).

Hash map’s balance shines.

Key Takeaways

• Hash Map: Count and check!
• Bit Vector: Bits save space!
• Palindromes: Odd counts matter.
• Python Tip: Dicts simplify—see [Python Basics](/python/basics).

Final Thoughts: Shuffle to Symmetry

LeetCode 266: Palindrome Permutation in Python is a string-shuffling puzzle. The hash map approach tallies with ease, while bit vector offers a compact twist. Want more palindrome fun? Try LeetCode 125: Valid Palindrome or LeetCode 131: Palindrome Partitioning. Ready to rearrange? Head to Solve LeetCode 266 on LeetCode and check that palindrome today!