Hard Problemsstringminimization

Min cost to sort strings using Reversals

Given an array of strings, where each string may be reversed at some given cost or left as it is, find the minimum total reversal cost that leaves the array sorted in lexicographic order.

Do this lesson first: house robber

Example input

strings = ["ca", "ab", "cb", "bd", "dc"], cost = [2, 1, 3, 2, 4]

Expected output

5

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[0][i] is the cheapest way to make strings 0 to i sorted with string i left as it is, and dp[1][i] the same with string i reversed; ∞ means no sorted arrangement ends that way. Those two rows are the layers. A third row, best, holds the smaller of the two: the answer if the array stopped at string i. Two layers rather than one because the only thing about strings 0 to i that string i + 1 cares about is how string i ended up spelled.

dp[r][i] = (r = 1 ? cost[i] : 0) + min over q in {0, 1} with form(i - 1, q) <= form(i, r) of dp[q][i - 1], or ∞ if neither q fits; best[i] = min(dp[0][i], dp[1][i])

Fix how string i ends up, kept or reversed. Its only link to everything before it is its neighbour: string i - 1's final spelling must not sort after it, and every string before that was already checked against string i - 1. So try both spellings of string i - 1, throw away a spelling that sorts after this one, take the cheaper survivor, and pay cost[i] on top if string i itself is reversed. This is the take-or-skip choice from the house-robber lesson, with one twist. House robber folds both options into one number and steps back two houses to avoid tracking which was taken; no fixed step back does that here, because whether string i + 1 fits depends on how string i is spelled, so the two options live on as two rows.

String 0 has no neighbour to agree with, so dp[0][0] = 0 and dp[1][0] = cost[0], and best[0] is the smaller. A kept or reversed cell reads only the column before it, and a best cell reads only the two cells above it, so the table fills one string at a time: kept, then reversed, then best. A cell is ∞ when no spelling of the string before it both fits and is finite; it stays in the table because the next string may still be able to follow the other row.

Tabulation, column by column. Each column costs four string comparisons, so the whole table is O(n × L) for strings of length up to L, and two rolling pairs of numbers are all you need. If both cells of the last column are ∞ the array cannot be sorted by reversals and the usual answer is -1; every prefix of this page's list can be sorted, so the slider never shows that. The best row exists so the answer sits in one fixed cell instead of being the smaller of two.

Time O(n × L), L the length of the longest stringSpace O(n), reducible to O(1) with two rolling pairs

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.

String 0 has no neighbour to agree with, so dp[0][0] = 0 and dp[1][0] = cost[0], and best[0] is the smaller. A kept or reversed cell reads only the column before it, and a best cell reads only the two cells above it, so the table fills one string at a time: kept, then reversed, then best. A cell is ∞ when no spelling of the string before it both fits and is finite; it stays in the table because the next string may still be able to follow the other row.

Rows ↓
Cols →

ca

ab

cb

bd

dc

kept

0

∞

3

6

5

reversed

2

3

6

5

10

best

0

3

5

Rows ↓string i is

Cols →string i as given

min-cost-to-sort-strings-using-reversals.ts

1function minReversalCost(strs, cost) {
2 const n = strs.length;
3 const form = (i, r) => (r ? [...strs[i]].reverse().join("") : strs[i]);
4 // rows: 0 kept, 1 reversed, 2 best of the two
5 const dp = [[0], [cost[0]], []];
6 for (let i = 0; i < n; i++) {
7 for (let r = 0; r < 3; r++) {
8 if (i === 0 && r < 2) continue; // the two bases on line 5
9 const options = r === 2
10 ? [dp[0][i], dp[1][i]]
11 : [0, 1].map((q) => (form(i - 1, q) <= form(i, r) ? dp[q][i - 1] + (r ? cost[i] : 0) : Infinity));
12 dp[r][i] = Math.min(...options);
13 }
14 }
15 return dp[2][n - 1] === Infinity ? -1 : dp[2][n - 1];
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

min-cost-to-sort-strings-using-reversals.ts

1function minReversalCost(strs, cost) {
2 const n = strs.length;
3 const form = (i, r) => (r ? [...strs[i]].reverse().join("") : strs[i]);
4 // rows: 0 kept, 1 reversed, 2 best of the two
5 const dp = [[0], [cost[0]], []];
6 for (let i = 0; i < n; i++) {
7 for (let r = 0; r < 3; r++) {
8 if (i === 0 && r < 2) continue; // the two bases on line 5
9 const options = r === 2
10 ? [dp[0][i], dp[1][i]]
11 : [0, 1].map((q) => (form(i - 1, q) <= form(i, r) ? dp[q][i - 1] + (r ? cost[i] : 0) : Infinity));
12 dp[r][i] = Math.min(...options);
13 }
14 }
15 return dp[2][n - 1] === Infinity ? -1 : dp[2][n - 1];
16}

Where people go wrong

Deciding left to right and leaving a string alone whenever you can, because leaving it costs nothing. On this list that keeps "ca" free and then has no move at "ab", since "ab" and "ba" both sort before "ca": the method reports the array impossible, where reversing "ca" for 2 makes room and the true answer for the first two strings is 3. Whether a string should be reversed depends on strings that come after it, which is exactly why both spellings have to stay alive as two rows until the end. The second trap is comparing string i only against string i - 1 as originally given, forgetting that it may have been reversed.

Require strictly increasing order.
Every <= in the fit test becomes <. The two rows, the costs and the order are unchanged; only which predecessors fit shrinks.
Report which strings to reverse, not just the cost.
The table is the same. Afterwards, walk back from the cheaper cell of the last column, at each column stepping to whichever predecessor gave the minimum, and note which row you were in.
Give each string a third option, say rotating it, at another cost.
Add a third layer. Each cell then tries all three spellings of the string before it, so a column costs nine comparisons instead of four; the shape of the recurrence does not change.

Stock Buy and Sell – At Most 2 Times Count of AP Subsequences