266. Palindrome Permutation
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 62.7%
Problem Breakdown
The problem asks us to determine if any permutation of a given string s can form a palindrome. A palindrome reads the same forwards and backwards. The input is a single string consisting of lowercase English letters, and the output should be a boolean value: true if a permutation exists that forms a palindrome, otherwise false.
Inputs:
- A string
s(1 <= s.length <= 5000), containing only lowercase English letters.
Outputs:
- A boolean value (
trueorfalse).
Implicit Constraints and Edge Cases:
- An empty string should return
truebecause it trivially forms a palindrome. - Strings with all identical characters (e.g., “aaa”) should return
true. - Strings with one character difference in the middle for odd-length strings (e.g., “civic”) should return
true.
Intuition
A brute-force approach would involve generating all permutations of the string and checking each one to see if it forms a palindrome. However, this is computationally expensive due to factorial time complexity relative to the length of the string.
The key insight is that for a string to be rearranged into a palindrome:
- If the string has an even length, every character must appear an even number of times.
- If the string has an odd length, exactly one character can appear an odd number of times (this would be the middle character in the palindrome), while all other characters must appear an even number of times.
This observation leads to a more efficient approach using a hash table to count character frequencies.
Approach
- Initialize a Hash Table: Use a dictionary to count the frequency of each character in the string.
- Count Frequencies: Iterate through the string and update the frequency count for each character.
- Check Parity of Frequencies:
- Initialize a counter
odd_countto zero. - Iterate through the frequency counts:
- If a character has an odd frequency, increment
odd_count. - If at any point
odd_countexceeds 1, returnfalsebecause more than one character cannot have an odd frequency in a valid palindrome permutation.
- If a character has an odd frequency, increment
- Initialize a counter
- Return Result: If
odd_countis 0 or 1 after checking all frequencies, returntrue.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through the string once to count character frequencies and then iterate through the frequency counts.
- Space Complexity: O(1) in terms of the number of unique characters (since there are only 26 lowercase English letters). Thus, it can be considered constant space.
Solution
def canPermutePalindrome(s: str) -> bool:
char_count = {}
# Count frequencies of each character
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1
odd_count = 0
# Check the number of characters with odd frequencies
for count in char_count.values():
if count % 2 != 0:
odd_count += 1
if odd_count > 1:
return False
return True
Edge Cases Handled
- Empty String: Returns
truebecause an empty string trivially forms a palindrome. - All Identical Characters: Returns
truebecause any permutation of the string will be a palindrome. - Single Odd Character in Middle for Odd-Length Strings: Returns
truebecause one character can have an odd frequency and still form a palindrome. - Multiple Odd Frequencies: Returns
falsebecause more than one character with an odd frequency cannot form a valid palindrome permutation.