Minimum Insertion Steps to Make a String Palindrome Solution
Minimum Insertion Steps to Make a String Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Insertion Steps to Make a String Palindrome is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, you may insert any character at any position in one step.
Return the minimum number of insertions needed to make s a palindrome.
Example 1
Input: s = "zzazz"
Output: 0
Explanation: Already a palindrome.
Example 2
Input: s = "mbadm"
Output: 2
Explanation: One answer is "mbdadbm".
Example 3
Input: s = "leetcode"
Output: 5
Constraints
1 <= s.length <= 500s consists of lowercase English letters.
Hints for Minimum Insertion Steps to Make a String Palindrome
Hint 1
Characters already forming a palindromic subsequence never need a partner inserted.
Hint 2
Every other character needs exactly one insertion to mirror it.
Hint 3
So the answer is
n - (longest palindromic subsequence).
How to solve Minimum Insertion Steps to Make a String Palindrome
Insertions only ever add mirrors. The characters you keep untouched must themselves read as a palindrome, so the best you can do is preserve the longest palindromic subsequence and mirror everything else.
Approach
- Compute the longest palindromic subsequence with the standard interval DP.
- Return
n - lps.
Why it works
Any palindrome containing s as a subsequence has length at least 2n - lps, and that bound is achievable by inserting a mirror for each of the n - lps unmatched characters. So n - lps insertions are both necessary and sufficient.
Complexity
- Time —
O(n²) - Space —
O(n²), reducible to O(n)
Pitfalls
- Counting mismatched pairs rather than unmatched characters double-counts.
- The greedy "reverse and diff" idea is really the LPS in disguise — computing
n - LCS(s, reverse(s))gives the same answer. - Filling the interval table in the wrong direction reads uninitialised cells.
Reference solution
Python
def minInsertions(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return n - dp[0][n - 1] if n else 0Java
public static int minInsertions(String s) {
int n = s.length();
if (n == 0) return 0;
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return n - dp[0][n - 1];
}C++
int minInsertions(string s) {
int n = (int) s.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return n - dp[0][n - 1];
}JavaScript
var minInsertions = function(s) {
const n = s.length;
if (n === 0) return 0;
const dp = [];
for (let i = 0; i < n; i++) dp.push(new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s.charAt(i) === s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return n - dp[0][n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming