Jobs

Interviews

Discussions

Palindrome Permutation II

Medium

Asked by:

13 views

Topics:

StringsRecursion

Given a string s, return all the palindromic permutations (without duplicates) of it. You may return the answer in any order. If s could not be arranged into a palindrome, return an empty list.

Example 1:

Input: s = "aabb"
Output: ["abba","baab"]

Example 2:

Input: s = "abc"
Output: []

Constraints:

1 <= s.length <= 16
s consists of lowercase English letters.

Try coding it in LeetCode

Palindrome Permutation II

Medium

Asked by:

13 views

Topics:

StringsRecursion

Example 1:

Input: s = "aabb"
Output: ["abba","baab"]

Example 2:

Input: s = "abc"
Output: []

Constraints:

1 <= s.length <= 16
s consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if no palindromic permutations are possible? An empty list?
Is the input string case-sensitive? Should I treat uppercase and lowercase letters differently?
Can the input string contain characters other than letters (e.g., spaces, numbers, punctuation)?
If multiple palindromic permutations exist, is there a specific order I should return them in (e.g., lexicographical order)?
What is the maximum length of the input string?

Brute Force Solution

Approach

The basic idea is to try every possible combination of letters from the input, and see if any of them form a palindrome. We'll generate all the arrangements and then check each one for palindrome-ness.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the input.
If more than one letter appears an odd number of times, it's impossible to make any palindromes, so stop.
If a single letter appears an odd number of times, that will be the middle letter of the palindrome.
Focus on the letters that appear an even number of times. These letters must be arranged around the central letter to form a palindrome.
Generate every single possible arrangement of these letters. This is the brute force part; try every possible ordering.
For each arrangement, add the central letter (if any) in the middle and then mirror the first half of the arrangement to create a full potential palindrome.
Check if the created string is actually a palindrome (reads the same forwards and backward).
If it is a palindrome, save it.
Repeat for every generated arrangement, removing duplicates from the final list of palindromes.

Code Implementation

def palindrome_permutation_brute_force(input_string):
    letter_counts = {}
    for letter in input_string:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    odd_counts = 0
    middle_character = ''
    for letter, count in letter_counts.items():
        if count % 2 != 0:
            odd_counts += 1
            middle_character = letter

    if odd_counts > 1:
        return []

    # Get characters to arrange for half of the palindrome
    half_string_characters = ''
    for letter, count in letter_counts.items():
        half_string_characters += letter * (count // 2)

    arrangements = set()

    def generate_permutations(characters, current_permutation):
        if not characters:
            arrangements.add(current_permutation)
            return

        for i in range(len(characters)):
            remaining_characters = characters[:i] + characters[i+1:]
            generate_permutations(remaining_characters, current_permutation + characters[i])

    generate_permutations(half_string_characters, '')

    palindromes = []
    for arrangement in arrangements:
        potential_palindrome = arrangement + middle_character + arrangement[::-1]
        # Check if the created string is a palindrome
        if potential_palindrome == potential_palindrome[::-1]:
            palindromes.append(potential_palindrome)

    return list(palindromes)

Big(O) Analysis

Time Complexity

O(n! * n) – Counting letter frequencies takes O(n) time, where n is the length of the input string. The core of the algorithm involves generating all permutations of the characters that appear an even number of times (or half their counts). The number of these permutations is approximately (n/2)!, where n is the length of the input string (we are dividing by two because each even appearing character only contributes half). Generating each permutation takes O(n/2) time. For each permutation, constructing the full palindrome and verifying it takes O(n) time. Thus, the dominant factor is generating permutations, leading to approximately (n/2)! permutations each requiring O(n) time to process giving a time complexity of O((n/2)! * n) which simplifies to O(n! * n). The odd occurring character is also considered, but it does not affect the asymptotic complexity.

Space Complexity

O(N) – The primary space consumption stems from storing the counts of each character in the input string, which can be represented by a hash map or an array of size proportional to the number of possible characters (at most N, where N is the length of the input string), and from the potential list of results. In the worst-case scenario, where there are many palindrome permutations, the list of results could grow up to O(N!), but because the total length of all generated strings is proportional to N * number of generated strings, it would be N * O(N!), which is an enormous upper bound. However, we can simplify the space requirements in relation to the plain English steps to O(N), as the bottleneck data structure grows linearly depending on the size of the input string.

Optimal Solution

Approach

The goal is to find all unique palindromes we can make by rearranging the input string. We avoid generating duplicates by only considering each character count, and then building permutations in a specific order.

Here's how the algorithm would work step-by-step:

First, count how many times each character appears in the string.
Check if a palindrome is even possible. A palindrome can only have one character that appears an odd number of times.
Extract the characters that appear an odd number of times (if any). If there are more than one odd character, then you know there is no possible arrangement to create a palindrome.
If there is only one odd character in the whole string, it must go in the very middle. We only need to work with one side, or half the string.
From the character counts, create a list of the 'half' of each character needed for one half of the palindrome. For example, if the character A appears 4 times, we need to create the permutations with AA.
Now, generate all unique arrangements (permutations) of these 'half' characters. To avoid duplicates, we only want to swap two characters to create new arrangements if the characters are different.
For each of these unique arrangements, we build the complete palindrome: reverse the current arrangement, put the single middle character (if any) in the middle, and add the reversed part to the end.

Code Implementation

def palindrome_permutations_two(input_string):
    character_counts = {}
    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    odd_characters = []
    for character, count in character_counts.items():
        if count % 2 != 0:
            odd_characters.append(character)

    # Palindromes can only have one character w/ odd frequency
    if len(odd_characters) > 1:
        return []

    middle_character = odd_characters[0] if odd_characters else ""

    half_characters = []
    for character, count in character_counts.items():
        half_characters.extend([character] * (count // 2))

    results = []

    def backtrack(current_permutation, used_indices):
        if len(current_permutation) == len(half_characters):
            palindrome = current_permutation + middle_character + current_permutation[::-1]
            results.append(palindrome)
            return

        for index in range(len(half_characters)):        
            if index not in used_indices:

                # Avoid duplicates - only swap different characters
                if index > 0 and half_characters[index] == half_characters[index - 1] and index - 1 not in used_indices:
                    continue

                current_permutation += half_characters[index]
                used_indices.add(index)

                backtrack(current_permutation, used_indices)

                used_indices.remove(index)
                current_permutation = current_permutation[:-1]

    # We keep track of indices to ensure permutations
    backtrack("", set())

    return results

Big(O) Analysis

Time Complexity

O(n * (n/2)!) – Let n be the length of the input string. Calculating character counts takes O(n) time. Finding the single odd character also takes O(n) time. Generating permutations of half the characters is the most expensive part. If there are k unique characters needed for half the string (where k is approximately n/2), generating all unique permutations will take O((n/2)!) time * n to reconstruct each palindrome. Therefore, the time complexity is dominated by the permutation generation, making the total time complexity O(n * (n/2)!).

Space Complexity

O(N) – The algorithm uses a hash map to store character counts, which takes O(N) space where N is the length of the input string. Additionally, it stores the 'half' characters in a list for permutation generation, which in the worst-case (all unique characters) could also be O(N). The recursion stack for generating permutations can reach a depth proportional to the number of 'half' characters, contributing O(N) space in the worst case. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty list since there are no permutations to generate.
Input string with only one character	Return a list containing the single character string itself as it's trivially a palindrome permutation.
Input string with a length of two and not a palindrome	Return an empty list as no palindrome permutation is possible.
Input string with characters that appear an odd number of times (more than one such character)	Return an empty list because palindrome permutation is impossible if there are more than one character with an odd count.
Input string containing only one distinct character repeated multiple times	Generate a list containing only that string since all permutations are the same and a palindrome.
Input string with extreme length approaching memory limits	Ensure the algorithm's memory usage is efficient; consider using iterative approach if recursion causes stack overflow for very long strings.
Input string with non-alphanumeric characters	Preprocess the string to either remove or normalize non-alphanumeric characters based on problem definition, or return an error if invalid.
Input string results in large number of permutations exceeding output list capacity	The algorithm needs to handle a large number of possible permutations without memory exhaustion, so consider optimization and algorithm efficiency.

Null or empty string input

How to Handle:

Return an empty list since there are no permutations to generate.

Input string with only one character

How to Handle:

Return a list containing the single character string itself as it's trivially a palindrome permutation.

Input string with a length of two and not a palindrome

How to Handle:

Return an empty list as no palindrome permutation is possible.

Input string with characters that appear an odd number of times (more than one such character)

How to Handle:

Return an empty list because palindrome permutation is impossible if there are more than one character with an odd count.

Input string containing only one distinct character repeated multiple times

How to Handle:

Generate a list containing only that string since all permutations are the same and a palindrome.

Input string with extreme length approaching memory limits

How to Handle:

Ensure the algorithm's memory usage is efficient; consider using iterative approach if recursion causes stack overflow for very long strings.

Input string with non-alphanumeric characters

How to Handle:

Preprocess the string to either remove or normalize non-alphanumeric characters based on problem definition, or return an error if invalid.

Input string results in large number of permutations exceeding output list capacity

How to Handle:

The algorithm needs to handle a large number of possible permutations without memory exhaustion, so consider optimization and algorithm efficiency.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if no palindromic permutations are possible? An empty list?
Is the input string case-sensitive? Should I treat uppercase and lowercase letters differently?
Can the input string contain characters other than letters (e.g., spaces, numbers, punctuation)?
If multiple palindromic permutations exist, is there a specific order I should return them in (e.g., lexicographical order)?
What is the maximum length of the input string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the input.
If more than one letter appears an odd number of times, it's impossible to make any palindromes, so stop.
If a single letter appears an odd number of times, that will be the middle letter of the palindrome.
Focus on the letters that appear an even number of times. These letters must be arranged around the central letter to form a palindrome.
Generate every single possible arrangement of these letters. This is the brute force part; try every possible ordering.
For each arrangement, add the central letter (if any) in the middle and then mirror the first half of the arrangement to create a full potential palindrome.
Check if the created string is actually a palindrome (reads the same forwards and backward).
If it is a palindrome, save it.
Repeat for every generated arrangement, removing duplicates from the final list of palindromes.

Code Implementation

def palindrome_permutation_brute_force(input_string):
    letter_counts = {}
    for letter in input_string:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    odd_counts = 0
    middle_character = ''
    for letter, count in letter_counts.items():
        if count % 2 != 0:
            odd_counts += 1
            middle_character = letter

    if odd_counts > 1:
        return []

    # Get characters to arrange for half of the palindrome
    half_string_characters = ''
    for letter, count in letter_counts.items():
        half_string_characters += letter * (count // 2)

    arrangements = set()

    def generate_permutations(characters, current_permutation):
        if not characters:
            arrangements.add(current_permutation)
            return

        for i in range(len(characters)):
            remaining_characters = characters[:i] + characters[i+1:]
            generate_permutations(remaining_characters, current_permutation + characters[i])

    generate_permutations(half_string_characters, '')

    palindromes = []
    for arrangement in arrangements:
        potential_palindrome = arrangement + middle_character + arrangement[::-1]
        # Check if the created string is a palindrome
        if potential_palindrome == potential_palindrome[::-1]:
            palindromes.append(potential_palindrome)

    return list(palindromes)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each character appears in the string.
Check if a palindrome is even possible. A palindrome can only have one character that appears an odd number of times.
Extract the characters that appear an odd number of times (if any). If there are more than one odd character, then you know there is no possible arrangement to create a palindrome.
If there is only one odd character in the whole string, it must go in the very middle. We only need to work with one side, or half the string.
From the character counts, create a list of the 'half' of each character needed for one half of the palindrome. For example, if the character A appears 4 times, we need to create the permutations with AA.
Now, generate all unique arrangements (permutations) of these 'half' characters. To avoid duplicates, we only want to swap two characters to create new arrangements if the characters are different.
For each of these unique arrangements, we build the complete palindrome: reverse the current arrangement, put the single middle character (if any) in the middle, and add the reversed part to the end.

Code Implementation

def palindrome_permutations_two(input_string):
    character_counts = {}
    for character in input_string:
        character_counts[character] = character_counts.get(character, 0) + 1

    odd_characters = []
    for character, count in character_counts.items():
        if count % 2 != 0:
            odd_characters.append(character)

    # Palindromes can only have one character w/ odd frequency
    if len(odd_characters) > 1:
        return []

    middle_character = odd_characters[0] if odd_characters else ""

    half_characters = []
    for character, count in character_counts.items():
        half_characters.extend([character] * (count // 2))

    results = []

    def backtrack(current_permutation, used_indices):
        if len(current_permutation) == len(half_characters):
            palindrome = current_permutation + middle_character + current_permutation[::-1]
            results.append(palindrome)
            return

        for index in range(len(half_characters)):        
            if index not in used_indices:

                # Avoid duplicates - only swap different characters
                if index > 0 and half_characters[index] == half_characters[index - 1] and index - 1 not in used_indices:
                    continue

                current_permutation += half_characters[index]
                used_indices.add(index)

                backtrack(current_permutation, used_indices)

                used_indices.remove(index)
                current_permutation = current_permutation[:-1]

    # We keep track of indices to ensure permutations
    backtrack("", set())

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty list since there are no permutations to generate.
Input string with only one character	Return a list containing the single character string itself as it's trivially a palindrome permutation.
Input string with a length of two and not a palindrome	Return an empty list as no palindrome permutation is possible.
Input string with characters that appear an odd number of times (more than one such character)	Return an empty list because palindrome permutation is impossible if there are more than one character with an odd count.
Input string containing only one distinct character repeated multiple times	Generate a list containing only that string since all permutations are the same and a palindrome.
Input string with extreme length approaching memory limits	Ensure the algorithm's memory usage is efficient; consider using iterative approach if recursion causes stack overflow for very long strings.
Input string with non-alphanumeric characters	Preprocess the string to either remove or normalize non-alphanumeric characters based on problem definition, or return an error if invalid.
Input string results in large number of permutations exceeding output list capacity	The algorithm needs to handle a large number of possible permutations without memory exhaustion, so consider optimization and algorithm efficiency.

Null or empty string input

How to Handle:

Return an empty list since there are no permutations to generate.

Input string with only one character

How to Handle:

Return a list containing the single character string itself as it's trivially a palindrome permutation.

Input string with a length of two and not a palindrome

How to Handle:

Return an empty list as no palindrome permutation is possible.

Input string with characters that appear an odd number of times (more than one such character)

How to Handle:

Return an empty list because palindrome permutation is impossible if there are more than one character with an odd count.

Input string containing only one distinct character repeated multiple times

How to Handle:

Generate a list containing only that string since all permutations are the same and a palindrome.

Input string with extreme length approaching memory limits

How to Handle:

Ensure the algorithm's memory usage is efficient; consider using iterative approach if recursion causes stack overflow for very long strings.

Input string with non-alphanumeric characters

How to Handle:

Preprocess the string to either remove or normalize non-alphanumeric characters based on problem definition, or return an error if invalid.

Input string results in large number of permutations exceeding output list capacity

How to Handle:

The algorithm needs to handle a large number of possible permutations without memory exhaustion, so consider optimization and algorithm efficiency.