DSA Tracker

Visualize

Minimum Insertion Steps to Make a String Palindrome

dp[i][j] = dp[i+1][j-1] when the ends match, else 1 + min of dropping either end

time O(n^2)space O(n^2)

Look at the two ends of the interval s[i..j]. If they already match, they need no insertion at all — the answer for the interval is exactly the answer for what is left in between. If they differ, at least one insertion is forced to fix ONE of the two ends, so try both and keep the cheaper interval: dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]). Filling i from the last character backward and j left to right guarantees every smaller interval the recurrence needs is already computed.

Details

Animated on: s = "mbadm" — find the minimum number of characters to insert anywhere in s so the result is a palindrome.

Problem:Minimum Insertion Steps to Make a String PalindromeHard

dp[i][j] = dp[i+1][j-1] when the ends match, else 1 + min of dropping either end

step 1 / 12

dp[i][j] = min insertions to make s[i..j] a palindrome

Every single character is already a palindrome on its own, so dp[i][i] = 0 for every i — this is the floor every longer interval builds up from.

Pseudocode
1FUNCTION minInsertions(s):
2  n <- LENGTH(s)
3  FOR i FROM 0 TO n-1: dp[i][i] <- 0
4  FOR i FROM n-1 DOWNTO 0:
5    FOR j FROM i+1 TO n-1:
6      IF s[i] = s[j]:
7        dp[i][j] <- dp[i+1][j-1]
8      ELSE:
9        dp[i][j] <- 1 + MIN(dp[i+1][j], dp[i][j-1])
10  RETURN dp[0][n-1]

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Every single character is already a palindrome on its own, so dp[i][i] = 0 for every i — this is the floor every longer interval builds up from.
  2. s[3]='d' != s[4]='m' — one end must gain an inserted match, so dp[3][4] = 1 + min(dp[4][4]=0, dp[3][3]=0) = 1.
  3. s[2]='a' != s[3]='d' — one end must gain an inserted match, so dp[2][3] = 1 + min(dp[3][3]=0, dp[2][2]=0) = 1.
  4. s[2]='a' != s[4]='m' — one end must gain an inserted match, so dp[2][4] = 1 + min(dp[3][4]=1, dp[2][3]=1) = 2.
  5. s[1]='b' != s[2]='a' — one end must gain an inserted match, so dp[1][2] = 1 + min(dp[2][2]=0, dp[1][1]=0) = 1.
  6. s[1]='b' != s[3]='d' — one end must gain an inserted match, so dp[1][3] = 1 + min(dp[2][3]=1, dp[1][2]=1) = 2.
  7. s[1]='b' != s[4]='m' — one end must gain an inserted match, so dp[1][4] = 1 + min(dp[2][4]=2, dp[1][3]=2) = 3.
  8. s[0]='m' != s[1]='b' — one end must gain an inserted match, so dp[0][1] = 1 + min(dp[1][1]=0, dp[0][0]=0) = 1.
  9. s[0]='m' != s[2]='a' — one end must gain an inserted match, so dp[0][2] = 1 + min(dp[1][2]=1, dp[0][1]=1) = 2.
  10. s[0]='m' != s[3]='d' — one end must gain an inserted match, so dp[0][3] = 1 + min(dp[1][3]=2, dp[0][2]=2) = 3.
  11. s[0]='m' matches s[4]='m' — both ends are already a palindrome pair, so dp[0][4] just inherits the interior: dp[0][4] = dp[1][3] = 2.
  12. dp[0][4] = 2 — the whole string "mbadm" needs 2 insertions to become a palindrome.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Insertion Steps to Make a String Palindrome in the editorAll Dynamic Programming problemsBack to roadmap