Leetcode - Palindrome Permutation Solution

Checking whether a string can be rearranged into a palindrome does not require generating its permutations. The deciding fact is the frequency of each character: at most one character may have an odd count.

The condition for a palindrome

Given a string, the task is to determine whether any permutation reads the same forward and backward, such as "racecar" or "aabbaa". Characters outside the middle must be paired, so every count must be even except possibly one count for an odd length palindrome.

Permutation generation baseline

My initial thought was to generate all permutations and check each one. This pseudocode assumes generatePermutations and isPalindrome helpers:

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;
}

Generating permutations costs O(n! × n), which becomes impractical quickly. For a string of length 10, it would inspect more than 3.6 million permutations.

Frequency condition and implementation

For an even length string, every character count must be even. For an odd length string, one odd count can occupy the middle and all other counts must be even. The algorithm thus counts odd frequencies instead of constructing permutations.

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;
}

Examples, complexity, and input details

An even count can be split across the two sides of a palindrome. One remaining character can sit in the middle when the string length is odd. More than one odd count leaves at least one character without a matching partner.

The frequency rule gives these results:

For "aab":

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

For "code":

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

For "aabb":

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

For "carerac":

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

The first implementation scans the string once and then scans the frequency map. With k unique characters, the time complexity is O(n + k), which is O(n) because k ≤ n. The map uses O(k) space.

The implementation treats uppercase and lowercase characters as different values. It also counts whitespace and special characters. An empty string has no odd frequencies, so the implementation returns true. These examples use ASCII strings. For Unicode text, both versions need the same definition of a character.

Single pass update and lesson

I can avoid the second map scan by updating the odd count whenever a character's frequency changes parity:

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 still runs in O(n) time and O(k) space, but it keeps the odd count state during the initial scan.

I was happy when I realized the palindrome property removed the need for permutation generation. Counting the state that matters is a general way to turn an exhaustive search into a linear scan.