Solution: Palindrome Permutation

Explore how to solve the palindrome permutation problem efficiently by learning to track character frequencies. Understand the key observations about character counts in palindromes and develop a solution with optimal time and space complexity. This lesson helps you implement a hash map approach to determine if any permutation of a string can form a palindrome, honing your problem-solving skills for coding interviews.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using frequency counting

Statement

For a given string, st, find whether or not a permutation of this string is a palindromePalindrome is a string of characters that reads the same forwards and backwards. For example, “ababa” and “xyxxyx” are palindromes.. You should return TRUE if such a permutation is possible and FALSE if it isn’t possible.

Constraints:

$1 \leq$ st.length $\leq 1000$
The string will contain lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive solution is to first compute all possible permutations of a given string and then iterate over each permutation to see if it’s a palindrome. We can use two pointers to traverse the computed permutation from the beginning and the end simultaneously, comparing each character at every step. If the two pointers point to the same character until they cross each other, the string is a palindrome.

The number of possible permutations for a string of length $n$ is $n!$ ...