Jobs

Interviews

Discussions

Minimum Insertion Steps to Make a String Palindrome

Hard

Google

2 views

Topics:

StringsDynamic Programming

You are given a string s. In one step, you can insert any character at any index of the string.

Your task is to return the minimum number of steps to make s a palindrome. A Palindrome String reads the same backward as forward.

Here are some examples to illustrate the problem:

If s = "zzazz", the output should be 0 because the string is already a palindrome.
If s = "mbadm", the output should be 2. Possible palindromes are "mbdadbm" or "mdbabdm".
If s = "leetcode", the output should be 5. A possible palindrome is "leetcodocteel".

Constraints:

The length of s is between 1 and 500, inclusive.
s consists of lowercase English letters.

Can you devise an algorithm to solve this problem efficiently? Explain the time and space complexity of your solution. Also, consider edge cases such as empty strings or strings that are already palindromes. Provide code in Java.

Minimum Insertion Steps to Make a String Palindrome

Hard

Google

2 views

Topics:

StringsDynamic Programming

You are given a string s. In one step, you can insert any character at any index of the string.

Your task is to return the minimum number of steps to make s a palindrome. A Palindrome String reads the same backward as forward.

Here are some examples to illustrate the problem:

If s = "zzazz", the output should be 0 because the string is already a palindrome.
If s = "mbadm", the output should be 2. Possible palindromes are "mbdadbm" or "mdbabdm".
If s = "leetcode", the output should be 5. A possible palindrome is "leetcodocteel".

Constraints:

The length of s is between 1 and 500, inclusive.
s consists of lowercase English letters.

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?
Can the input string contain special characters, spaces, or only alphanumeric characters?
If the input string is already a palindrome, should I return 0?
Are we concerned about case sensitivity (e.g., should 'Racecar' be considered a palindrome)?
Is the goal to find the *minimum* number of insertions, or just *a* number of insertions that make it a palindrome?

Brute Force Solution

Approach

The most straightforward, but slow, way to make a string a palindrome is to try inserting characters in every possible place. We check if we can make the string a palindrome after each set of insertions. We find the smallest set of insertions this way.

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

Start by trying no insertions at all and see if the original string is already a palindrome.
If it's not, try inserting one character at every possible location in the string. For each of these new strings, check if it's a palindrome.
If none of those are palindromes, try inserting two characters. For each spot, try inserting two of the same character, or two different characters, and check if that string is a palindrome.
Keep doing this, trying all combinations of inserting one more character than you previously tried at every location, and check for a palindrome.
Eventually, you will find a palindrome. The number of characters you needed to insert is the minimum number of insertions needed.

Code Implementation

def minimum_insertion_steps_palindrome_brute_force(input_string):
    string_length = len(input_string)

    # Check if the string is already a palindrome
    if input_string == input_string[::-1]:
        return 0

    for number_of_insertions in range(1, string_length + 1):
        possible_strings = generate_possible_strings(input_string, number_of_insertions)

        for possible_string in possible_strings:

            # Found a palindrome, return the insertion count
            if possible_string == possible_string[::-1]:
                return number_of_insertions

    return string_length

def generate_possible_strings(input_string, number_of_insertions):
    possible_strings = []
    generate_strings_recursive(input_string, number_of_insertions, "", possible_strings)
    return possible_strings

def generate_strings_recursive(input_string, number_of_insertions, current_string, possible_strings):
    if number_of_insertions == 0:
        # Base case: append original string and check if valid
        combined_string = current_string + input_string
        possible_strings.append(combined_string)
        return

    string_length = len(input_string)

    # Iterate through all possible insertion positions
    for insertion_index in range(string_length + 1):
        for char_code in range(ord('a'), ord('z') + 1):
            character_to_insert = chr(char_code)
            new_string = input_string[:insertion_index] + character_to_insert + input_string[insertion_index:]

            # Reduce insertion count
            remaining_string = new_string
            generate_strings_recursive(remaining_string, number_of_insertions - 1, "", possible_strings)

Big(O) Analysis

Time Complexity

O((2n)^n) – The algorithm explores all possible insertions to transform the given string into a palindrome. In the worst-case scenario, to make the string a palindrome, we may need to insert characters at almost every position. For each possible number of insertions (up to n insertions, where n is the length of the original string), we are considering every possible combination of characters to insert at every possible location. For each insertion, the algorithm has to generate all combinations, and the space of possible insertions grows exponentially, and for each of these combinations it checks whether the newly created string is a palindrome. The palindrome check itself takes O(n) time, but the number of insertion combinations totally dominates the running time. The total time complexity becomes O((2n)^n) because, in the worst case, we are inserting `n` characters at `n` possible locations, which leads to a very large amount of combinations. The algorithm checks each of these, hence exponential time complexity.

Space Complexity

O(N!) – The provided solution explores all possible insertions, which quickly leads to a combinatorial explosion of strings. In the worst case, we may have to generate and store a significant number of intermediate strings of length up to 2N, created from combinations of character insertions. The number of such strings that might need to be stored grows factorially with the input string's length N, where N is the length of the input string. Therefore, the auxiliary space required to store these intermediate strings is O(N!).

Optimal Solution

Approach

The key to solving this efficiently is recognizing the connection to the Longest Common Subsequence (LCS). Instead of brute-forcing insertions, we find the longest sequence that's already a palindrome within the original string. The number of insertions needed is then simply the difference between the original string's length and the length of that palindrome.

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

First, imagine reversing the original string.
Next, find the longest common subsequence between the original string and its reversed version. This longest common subsequence is the longest part of the string that's already a palindrome, possibly with other characters interleaved.
Finally, subtract the length of this longest common subsequence from the original string's length. The resulting difference is the minimum number of insertions needed to make the whole string a palindrome.

Code Implementation

def min_insertions(input_string): 
    string_length = len(input_string)
    reversed_string = input_string[::-1]

    # Initialize a DP table to store lengths of LCS.
    longest_common_subsequence_table = [[0] * (string_length + 1) for _ in range(string_length + 1)]

    # Building the dp table in bottom up manner.
    for i in range(1, string_length + 1):
        for j in range(1, string_length + 1):

            # If characters match, increase LCS length.
            if input_string[i - 1] == reversed_string[j - 1]:
                longest_common_subsequence_table[i][j] = longest_common_subsequence_table[i - 1][j - 1] + 1
            else:
                # Otherwise, take the max LCS length from previous results.
                longest_common_subsequence_table[i][j] = max(longest_common_subsequence_table[i - 1][j], longest_common_subsequence_table[i][j - 1])

    # The longest common subsequence length is palindrome.
    longest_palindrome_length = longest_common_subsequence_table[string_length][string_length]

    # Min insertions equals length diff.
    return string_length - longest_palindrome_length

Big(O) Analysis

Time Complexity

O(n²) – The core of the solution involves finding the Longest Common Subsequence (LCS) between the original string and its reversed version. This is typically done using dynamic programming with a 2D array of size n x n, where n is the length of the string. Computing each cell in this array requires constant time, but we have to fill n² cells. Therefore, the time complexity is O(n²).

Space Complexity

O(N^2) – The algorithm calculates the Longest Common Subsequence (LCS) between the original string and its reversed version. This LCS calculation typically uses dynamic programming, which involves constructing a 2D table to store intermediate results. Given a string of length N, this table will have dimensions N x N, requiring space proportional to N^2. Therefore, the auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string is already a palindrome.
String with a single character	Return 0, as a single-character string is already a palindrome.
String with two identical characters	Return 0, as it's already a palindrome.
String with two different characters	Return 1, as one insertion is required.
String that is already a palindrome	Return 0, as no insertions are needed.
String with all identical characters (e.g., 'aaaa')	Return 0, as the string is already a palindrome.
Very long string exceeding memory limits for dynamic programming table	Consider using an optimized space complexity dynamic programming approach or report that input size is too large.
String contains unicode or special characters	Ensure the comparison logic handles unicode or special characters correctly based on the problem's assumptions.

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?
Can the input string contain special characters, spaces, or only alphanumeric characters?
If the input string is already a palindrome, should I return 0?
Are we concerned about case sensitivity (e.g., should 'Racecar' be considered a palindrome)?
Is the goal to find the *minimum* number of insertions, or just *a* number of insertions that make it a palindrome?

Brute Force Solution

Approach

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

Start by trying no insertions at all and see if the original string is already a palindrome.
If it's not, try inserting one character at every possible location in the string. For each of these new strings, check if it's a palindrome.
If none of those are palindromes, try inserting two characters. For each spot, try inserting two of the same character, or two different characters, and check if that string is a palindrome.
Keep doing this, trying all combinations of inserting one more character than you previously tried at every location, and check for a palindrome.
Eventually, you will find a palindrome. The number of characters you needed to insert is the minimum number of insertions needed.

Code Implementation

def minimum_insertion_steps_palindrome_brute_force(input_string):
    string_length = len(input_string)

    # Check if the string is already a palindrome
    if input_string == input_string[::-1]:
        return 0

    for number_of_insertions in range(1, string_length + 1):
        possible_strings = generate_possible_strings(input_string, number_of_insertions)

        for possible_string in possible_strings:

            # Found a palindrome, return the insertion count
            if possible_string == possible_string[::-1]:
                return number_of_insertions

    return string_length

def generate_possible_strings(input_string, number_of_insertions):
    possible_strings = []
    generate_strings_recursive(input_string, number_of_insertions, "", possible_strings)
    return possible_strings

def generate_strings_recursive(input_string, number_of_insertions, current_string, possible_strings):
    if number_of_insertions == 0:
        # Base case: append original string and check if valid
        combined_string = current_string + input_string
        possible_strings.append(combined_string)
        return

    string_length = len(input_string)

    # Iterate through all possible insertion positions
    for insertion_index in range(string_length + 1):
        for char_code in range(ord('a'), ord('z') + 1):
            character_to_insert = chr(char_code)
            new_string = input_string[:insertion_index] + character_to_insert + input_string[insertion_index:]

            # Reduce insertion count
            remaining_string = new_string
            generate_strings_recursive(remaining_string, number_of_insertions - 1, "", possible_strings)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, imagine reversing the original string.
Next, find the longest common subsequence between the original string and its reversed version. This longest common subsequence is the longest part of the string that's already a palindrome, possibly with other characters interleaved.
Finally, subtract the length of this longest common subsequence from the original string's length. The resulting difference is the minimum number of insertions needed to make the whole string a palindrome.

Code Implementation

def min_insertions(input_string): 
    string_length = len(input_string)
    reversed_string = input_string[::-1]

    # Initialize a DP table to store lengths of LCS.
    longest_common_subsequence_table = [[0] * (string_length + 1) for _ in range(string_length + 1)]

    # Building the dp table in bottom up manner.
    for i in range(1, string_length + 1):
        for j in range(1, string_length + 1):

            # If characters match, increase LCS length.
            if input_string[i - 1] == reversed_string[j - 1]:
                longest_common_subsequence_table[i][j] = longest_common_subsequence_table[i - 1][j - 1] + 1
            else:
                # Otherwise, take the max LCS length from previous results.
                longest_common_subsequence_table[i][j] = max(longest_common_subsequence_table[i - 1][j], longest_common_subsequence_table[i][j - 1])

    # The longest common subsequence length is palindrome.
    longest_palindrome_length = longest_common_subsequence_table[string_length][string_length]

    # Min insertions equals length diff.
    return string_length - longest_palindrome_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string is already a palindrome.
String with a single character	Return 0, as a single-character string is already a palindrome.
String with two identical characters	Return 0, as it's already a palindrome.
String with two different characters	Return 1, as one insertion is required.
String that is already a palindrome	Return 0, as no insertions are needed.
String with all identical characters (e.g., 'aaaa')	Return 0, as the string is already a palindrome.
Very long string exceeding memory limits for dynamic programming table	Consider using an optimized space complexity dynamic programming approach or report that input size is too large.
String contains unicode or special characters	Ensure the comparison logic handles unicode or special characters correctly based on the problem's assumptions.