Pattern visualizer
Minimum Insertions to Make String Palindrome
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. Animated on: s = "mbadm" — find the minimum number of characters to insert anywhere in s so the result is a palindrome..
dp[i][j] = dp[i+1][j-1] when the ends match, else 1 + min of dropping either end
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.
1FUNCTION minInsertions(s):2 n <- LENGTH(s)3 FOR i FROM 0 TO n-1: dp[i][i] <- 04 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