Vultr DocsLatest Content

Minimum Insertion Steps to Make a String Palindrome

Updated on 12 June, 2025
Minimum Insertion Steps to Make a String Palindrome header image

Problem Statement

Given a string s, our task is to transform this string into a palindrome by inserting characters at any position within the string. Each character insertion counts as a single step. The challenge is to determine the minimum number of steps required to achieve this transformation.

A Palindrome is defined as a sequence of characters which reads the same backwards as it does forwards. This symmetry means that for any character at position i, there is a corresponding matching character at position n-i-1 in the string (where n is the length of the string).

Examples

Example 1

Input:

s = "zzazz"

Output:

0

Explanation:

The string "zzazz" is already a palindrome. We do not need any insertions.

Example 2

Input:

s = "mbadm"

Output:

2

Explanation:

The string can become "mbdadbm" or "mdbabdm" after 2 insertions.

Example 3

Input:

s = "vultrcode"

Output:

5

Explanation:

We need 5 insertions to make the string a palindrome.
One possible result is "vultrcodocrtluv" or similar valid palindromic forms.

Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Approach and Intuition

To solve this problem, it's crucial to understand how the lack of symmetry in the string contributes to the number of insertions needed.

Example-wise Breakdown

  1. Example 1: "zzazz"

    • This string is already a palindrome. When you read it from left to right or right to left, the characters align perfectly, so no insertions are needed.

  2. Example 2: "mbadm"

    • The characters at the endpoints do not match ("m" and "d"), indicating the need for steps to create symmetry. Inserting the characters "b" and "m" results in strings like "mbdadbm" or "mdbabdm", turning the input into a palindrome after 2 insertions.

  3. Example 3: "vultrcode"

    • The string has significant asymmetry. By analyzing potential symmetrical positions and inserting appropriate characters, a valid palindrome can be formed with 5 insertions.

Generalized Method

To generalize, the solution involves finding the longest palindromic subsequence (a sequence that appears in the same relative order, but not necessarily consecutively) within s. This longest sequence indicates parts of the string that would not need any changes. The difference between the length of this subsequence and the original string gives the minimum number of insertions required.

  • For instance, if s has a length of x and its longest palindromic subsequence has a length of y, the insertions required would be x - y.

By building on these observations, you can dynamically approach the problem, using calculations like dynamic programming to ensure all cases within the given constraints are efficiently handled.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int longestCommonSubsequence(string& x, string& y, int len1, int len2) {
        vector<int> currentRow(len2 + 1), lastRow(len2 + 1);

        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 || j == 0) {
                    currentRow[j] = 0;
                } else if (x[i - 1] == y[j - 1]) {
                    currentRow[j] = 1 + lastRow[j - 1];
                } else {
                    currentRow[j] = max(lastRow[j], currentRow[j - 1]);
                }
            }
            lastRow = currentRow;
        }

        return currentRow[len2];
    }

    int minInsertionsToMakePalindrome(string inputStr) {
        int length = inputStr.size();
        string reversedStr = inputStr;
        reverse(reversedStr.begin(), reversedStr.end());

        return length - longestCommonSubsequence(inputStr, reversedStr, length, length);
    }
};

This C++ solution addresses the problem of finding the minimum number of insertions required to transform a given string into a palindrome. The solution leverages the concept of the Longest Common Subsequence (LCS) to determine the number of insertions needed. Here's an overview of how the code works:

  • Define two primary methods within the Solution class: longestCommonSubsequence and minInsertionsToMakePalindrome.
  • The longestCommonSubsequence method computes the LCS length using dynamic programming. It employs a two-row method for space efficiency, where currentRow and lastRow represent the LCS lengths of the current and previous iterations, respectively.
  • In the minInsertionsToMakePalindrome method:
    • First, the method computes the reverse of the input string.
    • Then, it calls longestCommonSubsequence with the original and reversed strings to find out the LCS length.
    • Finally, it calculates the result as the difference between the input string's length and the LCS length. This difference represents the minimum number of insertions needed.

By exploiting the relationship between string reversals and palindromes, and using LCS to quantify the similarity, the solution efficiently determines the minimum insertions required for palindrome formation.

java 
class Solution {
    private int longestCommonSubsequence(String str1, String str2, int length1, int length2) {
        int[] currentDP = new int[length2 + 1];
        int[] previousDP = new int[length2 + 1];

        for (int i = 0; i <= length1; i++) {
            for (int j = 0; j <= length2; j++) {
                if (i == 0 || j == 0) {
                    currentDP[j] = 0;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    currentDP[j] = 1 + previousDP[j - 1];
                } else {
                    currentDP[j] = Math.max(previousDP[j], currentDP[j - 1]);
                }
            }
            System.arraycopy(currentDP, 0, previousDP, 0, length2 + 1);
        }

        return currentDP[length2];
    }

    public int minInsertions(String s) {
        int n = s.length();
        String reversedString = new StringBuilder(s).reverse().toString();

        return n - longestCommonSubsequence(s, reversedString, n, n);
    }
}

The Java code provided solves the problem of calculating the minimum number of insertions required to make a string a palindrome. The solution employs a dynamic programming approach based on the Longest Common Subsequence (LCS) between the original string and its reversed counterpart.

  • Define a longestCommonSubsequence private method that computes the LCS length between two strings. This method uses a dynamic programming table (currentDP and previousDP) to keep track of LCS values incrementally.

  • Implements two loops to compute values in the dynamic programming array:

    • If characters from str1 and str2 match at any given position, set the current position in currentDP based on the diagonal value from previousDP.
    • If they do not match, set the current currentDP value as the maximum value between the left and upper values in the dynamic arrays.

  • Updates the previousDP array after each row computation to maintain the LCS values obtained in the current iteration.

  • The minInsertions method calculates the minimum insertions needed:

    • Reverse the given string to compare with its original version.
    • Compute the LCS length between the original string and its reversed version using the previously defined method.
    • The result is the length of the original string minus the LCS value, which gives the minimum insertions required to transform the given string into a palindrome.

This approach ensures an efficient calculation of the necessary insertions by focusing on maximizing the palindromic subsequence through dynamic programming, eliminating redundant computations.

Comments

No comments yet.