Jobs

Interviews

Discussions

Smallest Palindromic Rearrangement I

Medium

Asked by:

26 views

Topics:

StringsGreedy Algorithms

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

Example 1:

Input: s = "z"

Output: "z"

Explanation:

A string of only one character is already the lexicographically smallest palindrome.

Example 2:

Input: s = "babab"

Output: "abbba"

Explanation:

Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.

Example 3:

Input: s = "daccad"

Output: "acddca"

Explanation:

Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
s is guaranteed to be palindromic.

Try coding it in LeetCode

Smallest Palindromic Rearrangement I

Medium

Asked by:

26 views

Topics:

StringsGreedy Algorithms

You are given a palindromic string s.

Return the lexicographically smallest palindromic permutation of s.

Example 1:

Input: s = "z"

Output: "z"

Explanation:

A string of only one character is already the lexicographically smallest palindrome.

Example 2:

Input: s = "babab"

Output: "abbba"

Explanation:

Rearranging "babab" → "abbba" gives the smallest lexicographic palindrome.

Example 3:

Input: s = "daccad"

Output: "acddca"

Explanation:

Rearranging "daccad" → "acddca" gives the smallest lexicographic palindrome.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
s is guaranteed to be palindromic.

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 is the maximum length of the input string `s`?
If a palindromic rearrangement is not possible, is returning an empty string the only acceptable output, or are there any other specific error indicators?
Is the input string guaranteed to contain only lowercase English letters, or could it contain other characters like numbers or symbols?
If multiple lexicographically smallest palindromes are possible (due to character frequency ties), which one should I return, or are they all considered valid?
Can the input string `s` be empty or null?

Brute Force Solution

Approach

The brute force method to find the smallest palindromic rearrangement involves creating all possible arrangements of the input and then checking if each arrangement is a palindrome. We want to find the smallest such palindrome if multiple exist. If no palindrome can be formed, we report failure.

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

First, list out every single possible arrangement of the letters in the given input.
Then, for each of those arrangements, check if it reads the same forwards and backward, which means checking if it is a palindrome.
If you find an arrangement that is a palindrome, remember it.
After checking every single arrangement, if you found at least one palindrome, choose the smallest one alphabetically. This is your answer.
However, if after checking every single arrangement, you didn't find any palindromes, then there's no solution.

Code Implementation

from itertools import permutations

def smallest_palindromic_rearrangement_brute_force(input_string):
    smallest_palindrome = None
    
    # Generate all possible permutations of the input string
    all_permutations = [''.join(permutation) for permutation in permutations(input_string)]
    
    for current_permutation in all_permutations:

        # Check if the current permutation is a palindrome
        if current_permutation == current_permutation[::-1]:

            #First palindromic permutation found
            if smallest_palindrome is None:
                smallest_palindrome = current_permutation

            #We found a new smaller palindromic permutation
            elif current_permutation < smallest_palindrome:
                smallest_palindrome = current_permutation

    return smallest_palindrome

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach first generates all possible permutations of the input string of length n. There are n! (n factorial) possible permutations. For each permutation, the algorithm checks if it's a palindrome by comparing characters from the beginning and end, which takes O(n) time. Thus, the overall time complexity is dominated by generating all permutations and checking if each is a palindrome. Therefore the time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the input string. The number of permutations for a string of length N is N!. Storing these permutations requires O(N!) space. While checking each permutation, we store individual permutations in memory, contributing to auxiliary space. Therefore, the space complexity is dominated by storing all the permutations.

Optimal Solution

Approach

To find the smallest palindromic rearrangement, we need to determine if a palindrome can even be formed from the given letters. If a palindrome is possible, we construct it by arranging the letters in ascending order from the outside in, mirroring the first half to create the second half.

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

First, count how many times each letter appears in the input.
Check if a palindrome can be made. A palindrome is only possible if at most one letter appears an odd number of times.
If a palindrome isn't possible, stop and indicate that.
If a palindrome is possible, create the first half of the palindrome by listing the letters in alphabetical order. Each letter should appear half as many times as it appears in the original input (rounding down).
If there's a letter that appears an odd number of times, put that letter in the middle of the palindrome.
Complete the palindrome by mirroring the first half (in reverse order) after the middle letter (if any).
The resulting arrangement is the smallest palindromic rearrangement.

Code Implementation

def find_smallest_palindromic_rearrangement(text):
    character_counts = {}
    for char in text:
        character_counts[char] = character_counts.get(char, 0) + 1

    odd_counts = 0
    odd_character = ''
    for char, count in character_counts.items():
        if count % 2 != 0:
            odd_counts += 1
            odd_character = char

    # Palindrome is impossible if more than one char has an odd count.
    if odd_counts > 1:
        return ''

    first_half = ''
    
    # Build the first half of the palindrome using sorted chars.
    characters = list(character_counts.keys())
    characters.sort()
    for char in characters:
        even_count = character_counts[char] // 2
        first_half += char * even_count

    # Place the odd character in the middle if it exists.
    middle_character = ''
    if odd_character:
        middle_character = odd_character * character_counts[odd_character]

    # Construct full palindrome by reversing the first half.
    second_half = first_half[::-1]
    return first_half + middle_character + second_half

Big(O) Analysis

Time Complexity

O(n) – The algorithm first counts the frequency of each character in the input string of length n. This takes O(n) time. Then, it iterates through the character counts to check if a palindrome is possible, which takes O(1) since the character set size is fixed. Constructing the first half of the palindrome takes O(n) time as, in the worst case, it has to iterate through all n characters and potentially create a new string. Finally, mirroring the first half also takes O(n) time. Thus, the dominant operations are counting frequencies and constructing the palindrome, both linear with respect to the input string length, resulting in O(n) overall.

Space Complexity

O(1) – The algorithm uses a character count data structure, which will have a fixed size (e.g., 26 for lowercase English letters) regardless of the input string length N. Other variables like the middle character and the half-string are constructed but their memory usage is bounded by the character set size, independent of N. Therefore, the auxiliary space used is constant and independent of the input size N.

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since an empty string is a palindrome.
Null string input	Treat the null input as invalid and return an empty string.
String with only one character	Return the original string as a single character is a palindrome.
String with two identical characters	Return the original string as it is already a palindrome.
String with two different characters that can form a palindrome (e.g., 'ab')	Sort the string alphabetically (e.g., 'ab' becomes 'ab').
String with characters that cannot form a palindrome (more than one character with an odd count)	Return an empty string if the character counts make forming a palindrome impossible.
String with a very large number of characters (performance considerations)	Use a character frequency map to optimize the palindrome construction process, ensuring O(n) time complexity.
String with all identical characters (e.g., 'aaaa')	Return the original string since it is already the smallest palindrome.

Empty string input

How to Handle:

Return an empty string immediately since an empty string is a palindrome.

Null string input

How to Handle:

Treat the null input as invalid and return an empty string.

String with only one character

How to Handle:

Return the original string as a single character is a palindrome.

String with two identical characters

How to Handle:

Return the original string as it is already a palindrome.

String with two different characters that can form a palindrome (e.g., 'ab')

How to Handle:

Sort the string alphabetically (e.g., 'ab' becomes 'ab').

String with characters that cannot form a palindrome (more than one character with an odd count)

How to Handle:

Return an empty string if the character counts make forming a palindrome impossible.

String with a very large number of characters (performance considerations)

How to Handle:

Use a character frequency map to optimize the palindrome construction process, ensuring O(n) time complexity.

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return the original string since it is already the smallest palindrome.

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 is the maximum length of the input string `s`?
If a palindromic rearrangement is not possible, is returning an empty string the only acceptable output, or are there any other specific error indicators?
Is the input string guaranteed to contain only lowercase English letters, or could it contain other characters like numbers or symbols?
If multiple lexicographically smallest palindromes are possible (due to character frequency ties), which one should I return, or are they all considered valid?
Can the input string `s` be empty or null?

Brute Force Solution

Approach

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

First, list out every single possible arrangement of the letters in the given input.
Then, for each of those arrangements, check if it reads the same forwards and backward, which means checking if it is a palindrome.
If you find an arrangement that is a palindrome, remember it.
After checking every single arrangement, if you found at least one palindrome, choose the smallest one alphabetically. This is your answer.
However, if after checking every single arrangement, you didn't find any palindromes, then there's no solution.

Code Implementation

from itertools import permutations

def smallest_palindromic_rearrangement_brute_force(input_string):
    smallest_palindrome = None
    
    # Generate all possible permutations of the input string
    all_permutations = [''.join(permutation) for permutation in permutations(input_string)]
    
    for current_permutation in all_permutations:

        # Check if the current permutation is a palindrome
        if current_permutation == current_permutation[::-1]:

            #First palindromic permutation found
            if smallest_palindrome is None:
                smallest_palindrome = current_permutation

            #We found a new smaller palindromic permutation
            elif current_permutation < smallest_palindrome:
                smallest_palindrome = current_permutation

    return smallest_palindrome

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 letter appears in the input.
Check if a palindrome can be made. A palindrome is only possible if at most one letter appears an odd number of times.
If a palindrome isn't possible, stop and indicate that.
If a palindrome is possible, create the first half of the palindrome by listing the letters in alphabetical order. Each letter should appear half as many times as it appears in the original input (rounding down).
If there's a letter that appears an odd number of times, put that letter in the middle of the palindrome.
Complete the palindrome by mirroring the first half (in reverse order) after the middle letter (if any).
The resulting arrangement is the smallest palindromic rearrangement.

Code Implementation

def find_smallest_palindromic_rearrangement(text):
    character_counts = {}
    for char in text:
        character_counts[char] = character_counts.get(char, 0) + 1

    odd_counts = 0
    odd_character = ''
    for char, count in character_counts.items():
        if count % 2 != 0:
            odd_counts += 1
            odd_character = char

    # Palindrome is impossible if more than one char has an odd count.
    if odd_counts > 1:
        return ''

    first_half = ''
    
    # Build the first half of the palindrome using sorted chars.
    characters = list(character_counts.keys())
    characters.sort()
    for char in characters:
        even_count = character_counts[char] // 2
        first_half += char * even_count

    # Place the odd character in the middle if it exists.
    middle_character = ''
    if odd_character:
        middle_character = odd_character * character_counts[odd_character]

    # Construct full palindrome by reversing the first half.
    second_half = first_half[::-1]
    return first_half + middle_character + second_half

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since an empty string is a palindrome.
Null string input	Treat the null input as invalid and return an empty string.
String with only one character	Return the original string as a single character is a palindrome.
String with two identical characters	Return the original string as it is already a palindrome.
String with two different characters that can form a palindrome (e.g., 'ab')	Sort the string alphabetically (e.g., 'ab' becomes 'ab').
String with characters that cannot form a palindrome (more than one character with an odd count)	Return an empty string if the character counts make forming a palindrome impossible.
String with a very large number of characters (performance considerations)	Use a character frequency map to optimize the palindrome construction process, ensuring O(n) time complexity.
String with all identical characters (e.g., 'aaaa')	Return the original string since it is already the smallest palindrome.

Empty string input

How to Handle:

Return an empty string immediately since an empty string is a palindrome.

Null string input

How to Handle:

Treat the null input as invalid and return an empty string.

String with only one character

How to Handle:

Return the original string as a single character is a palindrome.

String with two identical characters

How to Handle:

Return the original string as it is already a palindrome.

String with two different characters that can form a palindrome (e.g., 'ab')

How to Handle:

Sort the string alphabetically (e.g., 'ab' becomes 'ab').

String with characters that cannot form a palindrome (more than one character with an odd count)

How to Handle:

Return an empty string if the character counts make forming a palindrome impossible.

String with a very large number of characters (performance considerations)

How to Handle:

Use a character frequency map to optimize the palindrome construction process, ensuring O(n) time complexity.

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return the original string since it is already the smallest palindrome.