LeetCode Solutions Blog

Palindrome Permutation II

Number: 267

Difficulty: Medium

Paid? Yes

Companies: Meta, Cruise

Problem Description

Given a string s, the goal is to return all the palindromic permutations (without duplicates) that can be formed using the characters of s. If no palindromic permutation exists, return an empty list.

Key Insights

A valid palindrome reads the same forwards and backwards.
In a palindrome, at most one character can have an odd count.
Count the frequency of each character to verify if a palindrome can be created.
Use half of each character’s frequency to form one side of the palindrome, then mirror it.
Backtracking helps in generating unique permutations for the half-string.

Space and Time Complexity

Time Complexity: O(n!) in the worst-case due to generating permutations of the half-string.
Space Complexity: O(n) for the recursion stack and temporary storage during permutation.

Solution

The solution begins by counting character frequencies in the string. It checks whether more than one character has an odd count, which would make a palindromic permutation impossible. If valid, the algorithm identifies a potential middle character (if any) and builds a half-string composed of half the number of occurrences for each character. A backtracking approach is then employed to generate all unique permutations of the half-string. Each unique permutation is mirrored around the middle (if present) to form the complete palindrome.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python implementation with comments
from collections import Counter

def generatePalindromes(s: str):
    # Count frequency of each character in s
    char_count = Counter(s)
    mid = ""
    half_str = []
    
    # Check for the possibility of palindrome permutation and form half_str and mid if necessary
    for char, count in char_count.items():
        if count % 2 == 1:
            if mid:  # More than one odd count makes it impossible
                return []
            mid = char
        half_str.extend([char] * (count // 2))
    
    results = []
    used = [False] * len(half_str)
    half_str.sort()  # Sort to avoid duplicates

    def backtrack(path):
        # If the current permutation is complete, form the full palindrome
        if len(path) == len(half_str):
            palindrome = "".join(path) + mid + "".join(reversed(path))
            results.append(palindrome)
            return
        for i in range(len(half_str)):
            if used[i]:
                continue
            # Skip duplicates: if the same character was not used in previous position, continue
            if i > 0 and half_str[i] == half_str[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(half_str[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return results

# Example usage:
# print(generatePalindromes("aabb"))