Problem Informations

• Problem Index: 266
• Problem Link: Palindrome Permutation
• Topics: Hash Table, String, Bit Manipulation

Problem Description

Given a string $s$, return true if a permutation of the string could form a palindrome and false otherwise.

Example 1:

• Input: s = “code”
• Output: false

Example 2:

• Input: s = “aab”
• Output: true

Example 3:

• Input: s = “carerac”
• Output: true

Constraints:

• $1 \leq s.length \leq 5000$
• $s$ consists of only lowercase English letters.

Intuition

The problem of determining if any permutation of a given string can form a palindrome revolves around the frequency of characters in the string. A palindrome reads the same forwards and backwards, implying that each character’s frequency in the string should ideally be even, allowing them to be symmetrically arranged. The only exception is that one character can have an odd frequency if the palindrome’s length is odd. Therefore, the solution can be approached by checking that there is at most one character in the string with an odd frequency count.

Approach

The proposed solution uses a bitset to efficiently track the parity (odd or even count) of each character’s frequency in the input string. Here’s a step-by-step explanation of the approach:

1. Initialize a bitset: A bitset of size 26 (corresponding to the lowercase English alphabets) is initialized. Each bit in the bitset represents the parity of the count of a character (e.g., a flipped bit indicates that the character currently has an odd frequency count).

2. Iterate over the string: For each character in the string, calculate its position in the bitset by subtracting ‘a’ from the character. Flip the bit at this calculated position to update the parity of the character count.

3. Check parity condition: After processing all characters, check how many bits are set (i.e., how many characters have an odd frequency count). For the given string to have a permutation forming a palindrome, at most one bit should be set in the bitset. This condition corresponds to allowing one character to have an odd count, which is permissible for palindromes of odd length.

Thus, the solution is derived by verifying the bitset condition, returning true if there is at most one bit set and false otherwise. This approach efficiently utilizes bit manipulation, providing a time complexity of $O(n)$, where $n$ is the length of the string.

Code

C++

class Solution {
public:
    bool canPermutePalindrome(string s) {
        // Use a bitset to track the parity of character counts
        bitset<26> is_odd;
        
        // Iterate over each character in the string
        for (char c : s) {
            // Flip the corresponding bit for each character
            is_odd.flip(c - 'a');
        }
        
        // Check if there is at most one character with an odd count
        return (is_odd.count() < 2);
    }
};

Python

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # Use a set to track the parity of character counts
        is_odd = set()
        
        # Iterate over each character in the string
        for c in s:
            # Flip the corresponding bit for each character
            if c in is_odd:
                is_odd.remove(c)
            else:
                is_odd.add(c)
        
        # Check if there is at most one character with an odd count
        return len(is_odd) < 2

Complexity

• Time complexity: $O(n)$

  The time complexity of the algorithm is $O(n)$, where $n$ is the length of the input string $s$. The algorithm iterates over each character in the string exactly once in the for loop, flipping the corresponding bit in the bitset. The bitset.flip() and bitset.count() operations both run in constant time $O(1)$ in relation to the length of the alphabet (which is 26 for lowercase English letters), hence the overall time complexity is determined by the traversal of the string.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the bitset used to keep track of character counts has a fixed size of 26 bits, regardless of the input size. It does not scale with the size of the input string $s$ and therefore is considered constant space complexity.