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

Minimum Insertion Steps to Make a String Palindrome

Hard Dynamic ProgrammingMemoization LeetCode

Return the minimum number of insertions to make a string a palindrome.

Example: s = "leetcode" ā†’ Output: 5

Sample Input
ā€”
Sample Output
ā€”
Constraints
  • 1 <= s.length <= 500
  • s consists of lowercase English letters
Topics
Dynamic ProgrammingMemoization

LCS with Reverse

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

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