Leetcode - Palindrome Permutation Solution

Checking if a string can be rearranged into a palindrome seems like it would require generating all permutations, which would be O(n!) - completely impractical. But there's a much smarter way. You just need to count character frequencies. The insight? Palindromes have a very specific frequency pattern that we can check directly.

The key realization is that we don't need to generate any permutations. We can determine if a palindrome is possible by analyzing the character frequencies. If at most one character appears an odd number of times, we can form a palindrome.

Understanding the Problem

Given a string, determine if there's a permutation that's a palindrome. A palindrome reads the same forward and backward, like "racecar" or "aabbaa". The challenge is doing this efficiently without generating permutations.

My First Approach

My initial thought was to generate all permutations and check each one.

function canPermuteToPalindromeNaive(str) {
  // Generate all permutations (this is O(n!) - terrible!)
  const permutations = generatePermutations(str);

  for (let perm of permutations) {
    if (isPalindrome(perm)) {
      return true;
    }
  }
  return false;
}

This was O(n! × n), completely impractical! For a string of length 10, that's over 3.6 million permutations. I knew there had to be a better way.

The Insight: Frequency Pattern

Then I thought about what makes a palindrome:

• For even length: All characters appear an even number of times. We can pair them up: "aabb" → "abba"
• For odd length: One character appears once (goes in the middle), all others appear even times: "aab" → "aba"

So I don't need to generate permutations at all! I just need to count character frequencies and check how many appear an odd number of times. If at most one character has an odd frequency, we can form a palindrome.

The Solution

function canPermuteToPalindrome(str) {
  const frequencies = {};

  // Count frequency of each character
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    frequencies[char] = (frequencies[char] || 0) + 1;
  }

  // Count how many characters appear odd times
  let oddCount = 0;
  for (let char in frequencies) {
    if (frequencies[char] % 2 === 1) {
      oddCount++;
    }
  }

  // Can form palindrome if at most 1 character appears odd times
  return oddCount <= 1;
}

How It Works

The logic is straightforward:

• If all frequencies are even: We can pair them up symmetrically. Example: "aabb" → "abba"
• If one frequency is odd: That character goes in the middle. Example: "aab" → "aba"
• If more than one frequency is odd: We can't form a palindrome. Example: "abc" (all appear once, can't pair them all)

Step-by-Step Examples

Let me trace through some examples:

Example 1: "aab"

• Frequencies: a=2, b=1
• Odd count: 1 (only 'b')
• Result: true (can be "aba")

Example 2: "code"

• Frequencies: c=1, o=1, d=1, e=1
• Odd count: 4 (all characters)
• Result: false (can't form palindrome)

Example 3: "aabb"

• Frequencies: a=2, b=2
• Odd count: 0
• Result: true (can be "abba")

Example 4: "carerac"

• Frequencies: c=2, a=2, r=2, e=1
• Odd count: 1 (only 'e')
• Result: true (can be "racecar")

Complexity Analysis

Time Complexity: O(n)

• Single pass through the string to count frequencies: O(n)
• Single pass through the frequency map: O(k) where k is the number of unique characters
• In the worst case, k ≤ n, so O(n) overall

Space Complexity: O(k)

• We store frequencies for each unique character
• In the worst case, all characters are unique: O(n)
• Typically much less than O(n) if there are repeated characters

Common Pitfalls

When implementing this, watch out for:

1. Case sensitivity: "Aa" might be treated as two different characters depending on requirements
2. Whitespace: Decide whether spaces should be considered (usually yes for this problem)
3. Special characters: Make sure your frequency counting handles all characters correctly
4. Empty strings: An empty string is technically a palindrome

Optimized Version

We can optimize this further by using a single pass and tracking odd count as we go:

function canPermuteToPalindrome(str) {
  const frequencies = {};
  let oddCount = 0;

  for (let char of str) {
    frequencies[char] = (frequencies[char] || 0) + 1;
    
    // Update odd count on the fly
    if (frequencies[char] % 2 === 1) {
      oddCount++;
    } else {
      oddCount--;
    }
  }

  return oddCount <= 1;
}

This version is slightly more efficient as it avoids the second pass through the frequency map.

Key Takeaways

• Don't generate permutations if you can check properties instead
• Understanding the structure of what you're looking for (palindrome properties) helps
• Frequency counting is a powerful technique for string problems
• O(n!) can often be reduced to O(n) with the right insight
• This pattern appears in many string problems involving character analysis

I was really happy when I realized I didn't need to generate permutations. It's one of those moments where understanding the problem structure made the solution much simpler. This technique of analyzing properties instead of generating all possibilities is a powerful problem-solving approach that applies to many other problems.