Minimum Insertion Steps to Make a String Palindrome

Description

Minimum Insertion Steps to Make a String Palindrome

Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
A Palindrome String is one that reads the same backward as well as forward.

Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Constraints:

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

Approach - Tabulation 1D

• We convert the 2D to 1D
  • dp[j] (before overwrite) = dp[i+1][j]
  • dp[j-1] (just overwritten) = dp[i][j-1]
  • prev = dp[i+1][j-1]
• Think of this way when we do this 2D to 1D it is like we go through the same row again and again now if we want what was there on the same column in the last row then it is like asking what is the last value in current index as we only have one row
• If we ask what is the value one column back then it is just last index since we have one row but column are same as before
• O(n^2), O(n)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] dp = new int[n];
 
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int tmp = dp[j];
                if (s.charAt(i) == s.charAt(j))
                    dp[j] = prev;
                else
                    dp[j] = 1 + Math.min(dp[j], dp[j-1]);
                prev = tmp;
            }
        }
        return dp[n - 1];
    }
}

Approach - Tabulation 2D

• Similar approach everywhere just remember i-1 and j+1 because first loop backwards and second forward
• O(n^2), O(n^2)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
 
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1];
                else
                    dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
            }
        }
 
        return dp[0][n-1];
    }
}

Approach - Memoization 2D

• We just memoize the below solution using 2D DP
• O(n^2), O(n^2)

class Solution {
    int[][] dp;
    public int minInsertions(String s) {
        dp = new int[s.length() +1][s.length() + 1];
        for (int[] a: dp)
            Arrays.fill(a, -1);
 
        return solve(s, 0, s.length() - 1);
    }
 
    public int solve(String s, int i, int j) {
        if (i >= j)
            return 0;
        
        if (dp[i][j] != -1)
            return dp[i][j];
 
        if (s.charAt(i) == s.charAt(j))
            return dp[i][j] = solve(s, i+1, j-1);
        else
            return dp[i][j] = 1 + Math.min(solve(s, i+1, j), solve(s, i, j-1));
    }
}

Approach - Recursion

• We have simple tree where we take 2 pointer one from start and other from the end now what we do is if characters match at both index then we solve for i+1 and j-1
• If they are not equal then we have to do insertion and move to the next so we find minimum between i+1 and j-1 and add 1 for insertion
• O(2^n), O(1)

class Solution {
    public int minInsertions(String s) {
        return solve(s, 0, s.length() - 1);
    }
 
    public int solve(String s, int i, int j) {
        if (i >= j)
            return 0;
 
        if (s.charAt(i) == s.charAt(j))
            return solve(s, i+1, j-1);
        else
            return 1 + Math.min(solve(s, i+1, j), solve(s, i, j-1));
    }
}

---

Approach 1: Top-Down Recursion with Memoization ($O(N^2)$ Time, $O(N^2)$ Space)

Intuition

Use two pointers i and j starting at the ends of the string:

• If s.charAt(i) == s.charAt(j), no insertion is needed for these two characters. Move inward to solve solve(i + 1, j - 1).
• If they differ, try inserting a matching character on either the left or right side: $1+\min (\text{solve}(i+1,j),\text{solve}(i,j-1))$.

Memoize calculated subproblems in a 2D array to avoid redundant recursive calls.

import java.util.Arrays;
 
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(s, 0, n - 1, memo);
    }
 
    private int solve(String s, int i, int j, int[][] memo) {
        if (i >= j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
 
        if (s.charAt(i) == s.charAt(j)) {
            return memo[i][j] = solve(s, i + 1, j - 1, memo);
        } else {
            return memo[i][j] = 1 + Math.min(solve(s, i + 1, j, memo), solve(s, i, j - 1, memo));
        }
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — There are $O(N^2)$ distinct states $(i,j)$ filled in constant time.
• Space Complexity: $O(N^2)$ — For the memoization table and call stack depth of $O(N)$.

Approach 2: LCS Reduction with Space-Optimized DP (Optimal — $O(N^2)$ Time, $O(N)$ Space)

Intuition

The minimum insertions needed to make a string s a palindrome is:

$\text{Min Insertions}=N-\text{LPS}(s)$

where $\text{LPS}(s)$ is the Longest Palindromic Subsequence.

Finding $\text{LPS}(s)$ is equivalent to finding the Longest Common Subsequence (LCS) between s and its reverse string rev(s). Using rolling DP arrays optimizes space down to $O(N)$.

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();
 
        int[] dp = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            int prev = 0; // Stores dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
 
        return n - dp[n];
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — Nested loops run $N\times N$ times.
• Space Complexity: $O(N)$ — Uses a single 1D array of size $N+1$.

---

Easy Memory Rule

“Minimum insertions = $N-\text{LCS}(s,\text{reverse}(s))$“

Approach 3: Space-Optimized 1D Interval DP (Most Optimized — $O(N^2)$ Time, $O(N)$ Space)

Intuition

Build subproblems bottom-up by varying the substring bounds. For a substring s[i...j]:

• If s.charAt(i) == s.charAt(j), no insertion is required for the outer characters, so cost equals inner problem dp[i+1][j-1] (stored in prev).
• If s.charAt(i) != s.charAt(j), take $1+\min (\text{insert right},\text{insert left})$, which translates to $1+\min (dp[j],dp[j-1])$.

Filling backwards from $i=n-2$ down to $0$ compresses the 2D table into a single 1D array of size $N$, eliminating extra string allocations and reducing space complexity.

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] dp = new int[n];
 
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0; // Tracks dp[i+1][j-1]
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.min(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
 
        return dp[n - 1];
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — Two nested loops processing upper-triangular subproblems.
• Space Complexity: $O(N)$ — Uses a single 1D array of size $N$ with zero extra memory allocations.