Minimum Insertion Steps to Make a String Palindrome

Hard
579.

Minimum Insertion Steps to Make a String Palindrome

Minimum Insertion Steps to Make a String Palindrome is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

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 <= 500
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 500
  • s consists of lowercase English letters.

Hints for Minimum Insertion Steps to Make a String Palindrome

  1. Hint 1

    Characters already forming a palindromic subsequence never need a partner inserted.

  2. Hint 2

    Every other character needs exactly one insertion to mirror it.

  3. 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

  1. Compute the longest palindromic subsequence with the standard interval DP.
  2. 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 0

Java

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