Medium Problemspalindromestringinterval

Minimum insertions for palindrome

Given a string, find the minimum number of characters that must be inserted, anywhere within it, so that the resulting string reads the same forwards and backwards.

Do this lesson first: longest common subsequence

Example input

s = "abcdcb"

Expected output

1

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] = dp[i + 1][j - 1] if s[i] = s[j] (0 when j = i + 1), otherwise 1 + min(dp[i + 1][j], dp[i][j - 1])

Look at the two ends, as longest-palindromic-subsequence and the LCS lesson (/courses/dynamic-programming/longest-common-subsequence) do. If s[i] = s[j], they can stand as the outer pair of the finished palindrome exactly as they are, so they cost nothing and the whole cost is the inside's: dp[i + 1][j - 1], copied across unchanged. If they differ, they cannot face each other in the result, so one of them needs a new partner on the far side. A copy of s[i] inserted just after s[j] pairs with s[i] and leaves s[i + 1..j] to fix; a copy of s[j] inserted just before s[i] leaves s[i..j - 1]. Either way exactly one insertion is paid, so take the cheaper remainder and add 1. It is a min because only one of the two ends needs the new partner, and you want the cheaper one.

dp[i][i] = 0: one character is already a palindrome. A length-2 stretch with matching ends is 0 without reading anything, since its inside would sit below the diagonal; this page's string never puts two equal letters side by side, so that case never fires at any slider size, while longest-palindromic-subsequence's 'bb' does. Every other cell reads shorter stretches inside its own (below, to the left, or diagonally below-left), so filling by length makes each of them final before it is read.

Tabulation by stretch length: O(n²) cells, constant work at each, and two rows of space if i runs from n - 1 downwards. THE IDENTITY WITH longest-palindromic-subsequence: the answer always equals n minus the longest palindromic subsequence. Keep a longest palindromic subsequence and mirror every other character around it; and no plan does better, because the characters of s that an optimal plan did not need to mirror already form a palindromic subsequence. On 'abcdcb' the longest palindromic subsequence is 'bcdcb', 5 of 6 characters, and 6 - 5 = 1. This page does not use the identity. Its recurrence prices insertions directly from the ends and never mentions a subsequence, so it derives the same number independently. Work the identity out by brute force instead, n minus the longest palindrome among every subsequence of s, and it agrees with this table at every slider size, so the identity is tested here rather than assumed.

Time O(n²)Space O(n²), reducible to O(n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[i][i] = 0: one character is already a palindrome. A length-2 stretch with matching ends is 0 without reading anything, since its inside would sit below the diagonal; this page's string never puts two equal letters side by side, so that case never fires at any slider size, while longest-palindromic-subsequence's 'bb' does. Every other cell reads shorter stretches inside its own (below, to the left, or diagonally below-left), so filling by length makes each of them final before it is read.

Rows ↓
Cols →

0 a

1 b

2 c

3 d

4 c

5 b

0 a

0

1

2

3

2

1

1 b

·

0

1

2

1

0

2 c

·

0

1

0

1

3 d

·

0

1

2

4 c

·

0

1

5 b

·

0

Rows ↓row i: where the stretch of the string starts

Cols →column j: where it ends, so the cell is the fewest insertions that make s[i..j] a palindrome

minimum-insertions-for-palindrome.ts

1function minInsertions(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n));
4 for (let i = 0; i < n; i++) dp[i][i] = 0;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] === s[j]
9 ? (len === 2 ? 0 : dp[i + 1][j - 1])
10 : 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
11 }
12 }
13 return dp[0][n - 1];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

minimum-insertions-for-palindrome.ts

1function minInsertions(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n));
4 for (let i = 0; i < n; i++) dp[i][i] = 0;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] === s[j]
9 ? (len === 2 ? 0 : dp[i + 1][j - 1])
10 : 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
11 }
12 }
13 return dp[0][n - 1];
14}

Where people go wrong

Counting the mismatched mirror pairs, s[0] against s[n - 1], s[1] against s[n - 2] and so on, and calling that the answer. That count answers a different question, the fewest characters to REPLACE, and on this page's string it is wrong for insertions in both directions. At 6 characters, 'abcdcb', all three mirror pairs mismatch and the count says 3, yet one inserted 'a' finishes the job. At 7 characters, 'abcdcbx', only 'a' against 'x' mismatches and the count says 1, but the answer is 2. An insertion shifts everything after it, so the pairs a fixed mirror compares are not the pairs the finished palindrome matches. A greedy two-pointer walk that mirrors the left end at every mismatch fails too: it happens to get 1 at 6 characters, and at 7 it pays 6, one for every character before the 'x', where the table pays 2.

Delete characters instead of inserting them.
Same state, same recurrence, same answer. Deleting s[i] costs 1 and leaves s[i + 1..j], exactly what inserting its mirror did, so only the story told at a mismatched cell changes. Both equal n minus the longest palindromic subsequence.
Give each letter its own insertion cost.
The 1 splits into the cost of the letter being mirrored: at a mismatch dp[i][j] = min(cost(s[i]) + dp[i + 1][j], cost(s[j]) + dp[i][j - 1]). Matched ends, bases, state and fill order do not change. The identity with longest-palindromic-subsequence does not survive, since it only counts characters, which is the reason to know this page's direct recurrence and not just the identity.
Replace characters instead of inserting them.
No table at all. A replacement shifts nothing, so each mirror pair s[k], s[n - 1 - k] is settled on its own and the answer is the number of mismatched pairs. At 6 characters that count is 3 where insertions need 1: the pitfall above, seen from the other side.

Count Derangements Wildcard Pattern Matching