Domain 1EasyCORE

Palindrome Permutation

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`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

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 (true or false).

Implicit Constraints and Edge Cases:

  • An empty string should return true because 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

  1. Initialize a Hash Table: Use a dictionary to count the frequency of each character in the string.
  2. Count Frequencies: Iterate through the string and update the frequency count for each character.
  3. Check Parity of Frequencies:
    • Initialize a counter odd_count to zero.
    • Iterate through the frequency counts:
      • If a character has an odd frequency, increment odd_count.
      • If at any point odd_count exceeds 1, return false because more than one character cannot have an odd frequency in a valid palindrome permutation.
  4. Return Result: If odd_count is 0 or 1 after checking all frequencies, return true.

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 true because an empty string trivially forms a palindrome.
  • All Identical Characters: Returns true because any permutation of the string will be a palindrome.
  • Single Odd Character in Middle for Odd-Length Strings: Returns true because one character can have an odd frequency and still form a palindrome.
  • Multiple Odd Frequencies: Returns false because more than one character with an odd frequency cannot form a valid palindrome permutation.