Minimum number of insertions in a string to make it a palindrome

Problem: Minimum Insertion Steps to Make a String Palindrome

Problem Statement

Given a string s, return the minimum number of insertions required to make it a palindrome.
You may insert characters at any position in the string.

Intuition

To minimize insertions, we want to preserve the longest palindromic subsequence (LPS) already present in the string. The remaining characters (not part of this LPS) must be inserted to make the entire string a palindrome.

So the key formula becomes:

Minimum Insertions = s.length() - LPS(s)

We reduce this problem to finding the Longest Palindromic Subsequence (LPS).

Observation

To find the LPS, we compute the Longest Common Subsequence (LCS) of:

s and reverse(s)

Example

Input:

s = "mbadm"

Reverse:

"mdabm"

LCS(s, reverse) = "mam" (Length = 3)

Output:

Minimum insertions = 5 - 3 = 2

1. Recursion (LPS)

class Solution {
    public int minInsertions(String s) {
        return s.length() - lps(s, 0, s.length() - 1);
    }

    private int lps(String s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;

        if (s.charAt(i) == s.charAt(j)) {
            return 2 + lps(s, i + 1, j - 1);
        } else {
            return Math.max(lps(s, i + 1, j), lps(s, i, j - 1));
        }
    }
}

Time Complexity:

• Exponential: O(2^n)

• Not suitable for large inputs.

2. Memoization (Top-down DP)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        Integer[][] dp = new Integer[n][n];
        return n - lps(s, 0, n - 1, dp);
    }

    private int lps(String s, int i, int j, Integer[][] dp) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (dp[i][j] != null) return dp[i][j];

        if (s.charAt(i) == s.charAt(j)) {
            dp[i][j] = 2 + lps(s, i + 1, j - 1, dp);
        } else {
            dp[i][j] = Math.max(lps(s, i + 1, j, dp), lps(s, i, j - 1, dp));
        }

        return dp[i][j];
    }
}

Time Complexity: O(n^2)

Space Complexity: O(n^2) (due to recursion stack and memo table)

3. Tabulation (Bottom-up DP using LCS)

class Solution {
    public int minInsertions(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        return s.length() - lcs(s, rev);
    }

    private int lcs(String a, String b) {
        int n = a.length();
        int[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][n]; // LPS length
    }
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Summary

Dry Run

Input: s = "mbadm"