Minimum Insertion Steps to Make a String Palindrome solution and explanation
IBM
Google
9 more videos on this problem
Minimum Insertion Steps to Make a String Palindrome | Recur+Memo | GOOGLE | Leetcode-1312 🧑🏻💻codestorywithMIK · 16:36 · 10K views
1312. Minimum Insertion Steps to Make a String Palindrome | LEETCODE HARD | DYNAMIC PROGRAMMINGcode Explainer · 8:02 · 6K views
Leetcode 1312: Minimum Insertion Steps to Make a String Palindrome (Leetcode Hard)Algorithms Casts · 33:19 · 3K views
LeetCode 1312. Minimum Insertion Steps to Make a String PalindromeHappy Coding · 27:05 · 2K views
1312. Leetcode Minimum Insertion Steps to Make a String PalindromeGET SDE READY · 17:25 · 1K views
Minimum Insertion Steps to Make a String Palindrome - Leetcode 1312 - PythonTechError · 10:46 · 1K views
Minimum Insertion Steps to Make a String Palindrome - LeetCode 1312 - Python SolutionCode with Carter · 7:25 · 1K views
1312. Minimum Insertion Steps to Make a String Palindrome | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 18:48 · 607 views
Daily Leetcode #1117: Apr 22, 2023 - 1312. Minimum Insertion Steps to Make a String PalindromeProgramming Live with Larry · 7:01 · 540 views
DP 29. Minimum Insertions to Make String Palindrometake U forward · 12:00 · 267K views
The problem
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 <= 500sconsists of lowercase English letters.
Approach overview
Problem Overview: Given a string s, compute the minimum number of characters you must insert anywhere in the string so the final string becomes a palindrome. Insertions can be made at any position, but existing characters cannot be removed or reordered.
Approach 1: Dynamic Programming (Longest Palindromic Subsequence) (Time: O(n^2), Space: O(n^2))
The key observation: the minimum insertions required equals n - LPS, where LPS is the length of the Longest Palindromic Subsequence. A subsequence that is already palindromic does not require changes; you only insert characters to mirror the missing parts. Compute LPS by finding the Longest Common Subsequence between the string and its reverse. Use a 2D DP table where dp[i][j] stores the LCS length for prefixes of the original and reversed string. The final answer becomes n - dp[n][n]. This approach is stable, easy to reason about, and widely expected in interviews involving dynamic programming and string problems.
Approach 2: Recursion with Memoization (Time: O(n^2), Space: O(n^2))
Work directly on the palindrome property using two pointers. Define a recursive function on substring indices (i, j). If s[i] == s[j], both characters can stay in the palindrome, so recurse on (i+1, j-1). If they differ, you must insert a matching character on either side, which means taking 1 + min(f(i+1, j), f(i, j-1)). Memoize results in a 2D cache to avoid recomputation of overlapping subproblems. This formulation mirrors how palindromes are built from both ends and is a natural application of dynamic programming over substrings.
Recommended for interviews: The Longest Palindromic Subsequence transformation is usually the expected explanation because it reduces the problem to a well-known DP pattern. Mentioning the recursive two‑pointer formulation shows deeper understanding of palindrome structure, but implementing the LPS DP tends to be cleaner and easier to debug under time pressure.
Approach 1: Approach 1: Dynamic Programming (Longest Palindromic Subsequence)
This approach utilizes dynamic programming to find the longest palindromic subsequence in the given string. The minimum number of insertions required is the difference between the length of the string and this subsequence. The idea is to consider characters from both ends of the string and make decisions accordingly using a DP table.
def minInsertions(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(1, n):
for i in range(n - length):
j = i + length
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
print(minInsertions("mbadm"))public class MinInsertions {
public static int minInsertions(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int len = 1; len < n; len++) {
for (int i = 0, j = len; j < n; i++, 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];
}
public static void main(String[] args) {
System.out.println(minInsertions("mbadm"));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int minInsertions(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 1; len < n; ++len) {
for (int i = 0, j = len; j < n; ++i, ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
int main() {
cout << minInsertions("mbadm") << endl;
return 0;
}function minInsertions(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let len = 1; len < n; len++) {
for (let i = 0, j = len; j < n; i++, j++) {
if (s[i] === s[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];
}
console.log(minInsertions("mbadm"));#include <stdio.h>
#include <string.h>
int minInsertions(char *s) {
int n = strlen(s);
int dp[n][n];
memset(dp, 0, sizeof(dp));
for (int len = 1; len < n; len++) {
for (int i = 0, j = len; j < n; i++, j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = 1 + ((dp[i+1][j] < dp[i][j-1]) ? dp[i+1][j] : dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
int main() {
char s[] = "mbadm";
printf("%d\n", minInsertions(s));
return 0;
}using System;
public class Solution {
public int MinInsertions(string s) {
int n = s.Length;
int[,] dp = new int[n, n];
for (int len = 1; len < n; len++) {
for (int i = 0, j = len; j < n; i++, j++) {
if (s[i] == s[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];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinInsertions("mbadm"));
}
}In Python, we create a list of lists as our DP table. For each substring length, we determine the least insertions needed by comparing characters from both ends, adjusting counts based on matches or not.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 2: Approach 2: Recursion with Memoization
This approach leverages a recursive function to explore all possibilities, but uses memoization to cache results of previously computed subproblems. This reduces redundant calculations.
def solve(s, left, right, dp):
if left >= right:
return 0
if dp[left][right] != -1:
return dp[left][right]
if s[left] == s[right]:
dp[left][right] = solve(s, left + 1, right - 1, dp)
else:
dp[left][right] = 1 + min(solve(s, left + 1, right, dp), solve(s, left, right - 1, dp))
return dp[left][right]
def minInsertions(s):
n = len(s)
dp = [[-1] * n for _ in range(n)]
return solve(s, 0, n - 1, dp)
print(minInsertions("mbadm"))import java.util.Arrays;
public class RecurMemo {
int[][] dp;
public int solve(String s, int left, int right) {
if (left >= right) return 0;
if (dp[left][right] != -1) return dp[left][right];
if (s.charAt(left) == s.charAt(right))
dp[left][right] = solve(s, left + 1, right - 1);
else
dp[left][right] = 1 + Math.min(solve(s, left + 1, right), solve(s, left, right - 1));
return dp[left][right];
}
public int minInsertions(String s) {
int n = s.length();
dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, -1);
return solve(s, 0, n - 1);
}
public static void main(String[] args) {
RecurMemo recurMemo = new RecurMemo();
System.out.println(recurMemo.minInsertions("mbadm"));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<vector<int>> dp;
int solve(const string &s, int left, int right) {
if (left >= right) return 0;
if (dp[left][right] != -1) return dp[left][right];
if (s[left] == s[right])
dp[left][right] = solve(s, left + 1, right - 1);
else
dp[left][right] = 1 + min(solve(s, left + 1, right), solve(s, left, right - 1));
return dp[left][right];
}
int minInsertions(string s) {
int n = s.length();
dp.resize(n, vector<int>(n, -1));
return solve(s, 0, n - 1);
}
int main() {
cout << minInsertions("mbadm") << endl;
return 0;
}function solve(s, left, right, dp) {
if (left >= right) return 0;
if (dp[left][right] !== -1) return dp[left][right];
if (s[left] === s[right]) {
dp[left][right] = solve(s, left + 1, right - 1, dp);
} else {
dp[left][right] = 1 + Math.min(solve(s, left + 1, right, dp), solve(s, left, right - 1, dp));
}
return dp[left][right];
}
function minInsertions(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(-1));
return solve(s, 0, n - 1, dp);
}
console.log(minInsertions("mbadm"));#include <stdio.h>
#include <string.h>
#define MAX 500
int dp[MAX][MAX];
int solve(char *s, int left, int right) {
if (left >= right)
return 0;
if (dp[left][right] != -1)
return dp[left][right];
if (s[left] == s[right])
dp[left][right] = solve(s, left + 1, right - 1);
else
dp[left][right] = 1 + (solve(s, left + 1, right) < solve(s, left, right - 1) ? solve(s, left + 1, right) : solve(s, left, right - 1));
return dp[left][right];
}
int minInsertions(char *s) {
memset(dp, -1, sizeof(dp));
return solve(s, 0, strlen(s) - 1);
}
int main() {
char s[] = "mbadm";
printf("%d\n", minInsertions(s));
return 0;
}using System;
public class RecurMemo {
int[,] dp;
private int Solve(string s, int left, int right) {
if (left >= right) return 0;
if (dp[left, right] != -1) return dp[left, right];
if (s[left] == s[right])
dp[left, right] = Solve(s, left + 1, right - 1);
else
dp[left, right] = 1 + Math.Min(Solve(s, left + 1, right), Solve(s, left, right - 1));
return dp[left, right];
}
public int MinInsertions(string s) {
int n = s.Length;
dp = new int[n, n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dp[i, j] = -1;
return Solve(s, 0, n - 1);
}
public static void Main(string[] args) {
RecurMemo recurMemo = new RecurMemo();
Console.WriteLine(recurMemo.MinInsertions("mbadm"));
}
}The Python version employs recursion with memoization. A nested list dp is used to store already computed results, avoiding unnecessary calculations.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 3: Default Approach
func minInsertions(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= j {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := 1 << 30
if s[i] == s[j] {
ans = dfs(i+1, j-1)
} else {
ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
}
f[i][j] = ans
return ans
}
return dfs(0, n-1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming (Longest Palindromic Subsequence) | Time Complexity: O(n^2) |
| Approach 2: Recursion with Memoization | Time Complexity: O(n^2) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Longest Palindromic Subsequence via LCS) | O(n^2) | O(n^2) | Standard interview solution; reliable for strings up to typical DP constraints |
| Recursion with Memoization (Two-Pointer Substring DP) | O(n^2) | O(n^2) | When reasoning directly about palindrome construction from both ends |
Frequently asked questions
Is Minimum Insertion Steps to Make a String Palindrome easy or hard?
The problem is generally classified as Hard because it requires recognizing the transformation to the Longest Palindromic Subsequence problem or implementing substring dynamic programming. Candidates unfamiliar with LCS-based reductions often struggle to reach the optimal O(n^2) solution.
Minimum Insertion Steps to Make a String Palindrome Python/Java solution
Python and Java implementations typically build a DP table for the Longest Common Subsequence between the string and its reversed version. After computing the LCS length, subtract it from the string length to get the minimum insertions. Both implementations run in O(n^2) time.
How to solve Minimum Insertion Steps to Make a String Palindrome in O(n)?
An O(n) solution is not known for the general case. The problem requires evaluating relationships between many substring pairs, which leads to O(n^2) dynamic programming states. The best practical solution currently runs in O(n^2) time using DP.
What is the best approach for Minimum Insertion Steps to Make a String Palindrome?
The most common approach uses Dynamic Programming with the Longest Palindromic Subsequence (LPS). Compute LPS by finding the Longest Common Subsequence between the string and its reverse. The minimum insertions required equals n minus the LPS length. This runs in O(n^2) time and O(n^2) space.
Is Minimum Insertion Steps to Make a String Palindrome asked at Google/Amazon/Meta?
Palindrome dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving palindromic subsequences, substring DP, or minimum insertions/deletions are common in mid to senior algorithm rounds.
What data structure is used in Minimum Insertion Steps to Make a String Palindrome?
The solution mainly relies on a 2D dynamic programming table that stores results for substring ranges or prefix pairs. The algorithm also uses string manipulation and sometimes two-pointer recursion with memoization stored in arrays or hash maps.
What is the time complexity of Minimum Insertion Steps to Make a String Palindrome?
The optimal solution runs in O(n^2) time because it fills a dynamic programming table for all substring pairs. Both the LPS-based solution and the memoized recursion approach evaluate O(n^2) states. Each state is computed in constant time.