Minimum Insertion Steps to Make a String Palindrome Hard 0 attempts
LeetCode ↗

Minimum Insertion Steps to Make a String Palindrome

Hard Dynamic ProgrammingMemoization LeetCode

Given a string s, work out the fewest characters you'd need to insert — at any positions — so that the resulting string reads the same forwards and backwards.

Input Format
Implement minInsertions(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s = "leetcode"
Output
5

Example 2

Input
s = "zzazz"
Output
0
Constraints
  • 1 <= s.length <= 500
  • s consists of lowercase English letters
Test Cases (2)
Case 1
Args: ["leetcode"] Expected: 5
Case 2
Args: ["zzazz"] Expected: 0
Topics
Dynamic ProgrammingMemoization

LCS with Reverse

Answer = n - LPS length (longest palindromic subsequence = LCS(s, reverse(s))).

javascript
function minInsertions(s) {
  const n = s.length, t = s.split('').reverse().join('');
  const dp = Array(n+1).fill(0);
  for (let i = 1; i <= n; i++) {
    const prev = [...dp];
    for (let j = 1; j <= n; j++)
      dp[j] = s[i-1]===t[j-1] ? prev[j-1]+1 : Math.max(dp[j-1], prev[j]);
  }
  return n - dp[n];
}

Time: O(n²) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript