DP on grids and strings

The payout batch that stalled on a stranger's name

A nightly batch sends about 50,000 merchant payouts. Before each one, a check compares the name the merchant typed with the name the bank returns. Small differences are fine: "Ramkrishna" and "Ramakrishna" are one insertion apart, and the rule allows at most two edits.

The obvious check is a recursive function, edits(i, j), which returns the fewest edits between the first i letters of one name and the first j letters of the other. When the last letters differ, it tries three edits (delete, insert or replace) and recurses on each. Similar names finish fast, because matching letters need no branching. Then one night the batch stops moving. It is stuck on a payout where the typed name and the bank's name belong to different people: two 12-letter names that share no letter. When the names disagree everywhere, every call makes three more calls. Run that one pair with a counter and it makes 377,393,953 calls.

Now count the different questions the function can be asked. i runs from 0 to 12, and so does j, so there are 13 × 13 = 169 different questions. The recursion asks them 377 million times in total.

Pause and predict What should edits(i, j) turn into?

Two prefixes, one table

In 1D DP, dp[i] was the answer for a prefix, built from shorter prefixes. With two strings, a smaller problem can shorten either string or both. So the state is a pair of prefixes, s[:i] and t[:j], and the answers fill a two-dimensional table.

The method is the same as in 1D: say what a cell means, find the last choice, set the base cells, and choose an order. Only the shape of the table changes.

Here is why those three cells are enough. Look at the last letters, s[i - 1] and t[j - 1]. In every problem in this family, either both are used or at least one of them is dropped. Each case leaves a smaller pair of prefixes, and those smaller pairs are exactly three cells: the diagonal (both letters gone), the cell above (s[i - 1] gone) and the cell to the left (t[j - 1] gone).

Pause and predict Longest common subsequence. The last letters s[i - 1] and t[j - 1] are equal. What is dp[i][j]?

An extra empty row and column

Row 0 stands for the empty prefix of s, and column 0 for the empty prefix of t. Their answers are known without any work: an empty string has no letters in common with anything, and turning "abc" into "" takes three deletes. With this extra row and column in place, every real cell has all three neighbours, and the loop needs no special case for the first letter.

Pause and predict With the empty row and column in place, which letters does cell (i, j) compare?

Three neighbours, three meanings

The table has the same shape in every problem here. What changes is what each of the three neighbours means, and that is the part to say out loud in an interview.

Grids are the same table

Pause and predict A robot moves only right or down. How many routes cross a 3 by 4 grid, top-left to bottom-right?

A cell reads only its own row and the row above, so you can keep a single row and overwrite it. Just before row[c] += row[c - 1] runs, row[c] still holds the value from the row above, and row[c - 1] already holds the new value for the cell to the left. This only works if you go left to right; going the other way, the left neighbour would still hold the old row's value. The same single-row trick works for the string tables, with one extra variable that saves the diagonal value before it is overwritten.

Palindromes: one string, two ends

Here the two indices are the two ends of one string. s[l..r] is a palindrome when s[l] == s[r] and the part inside them is also a palindrome. The inside part is shorter, so the table is filled in order of length. Expanding outward from each centre uses the same rule without storing a table:

How to recognise it

The strongest signal is two sequences that are worked through together, such as two strings compared letter by letter. The second is a grid where moves go in only two directions, such as right and down. The third is the phrase "palindromic substring".

Pause and predict Which of these wants a 2D table?

Four that only look like it

• One sequence with a choice at each index. That is 1D DP. If only one index ever moves, a second dimension adds nothing.
• A grid you may cross in any direction, or a request for the fewest steps. Routes can loop, so no fill order works. Use BFS from graphs, or Dijkstra when moves have costs.
• A contiguous piece that grows and shrinks. When a rule tells you when to grow and when to shrink, that is a sliding window. LCS skips letters, so no window can describe it.
• A request to list every answer instead of counting or optimising. That is backtracking, because the table stores only one number per pair of prefixes.

Where it bites

Pause and predict In Python, dp = [[0] * 3] * 2, then dp[0][0] = 1. What does print(dp) show?

• Getting the offset wrong. Cell (i, j) compares s[i - 1] and t[j - 1]. Comparing s[i] reads the next letter and eventually runs past the end of the string.
• Copying base cases from another problem. LCS sets row 0 and column 0 to 0. Edit distance sets them to j and i. Regular expressions must compute row 0 properly, because a pattern like "a*" can match the empty string.
• Taking the diagonal on a mismatch in LCS. That drops both letters when only one of them needs to go.
• Filling a single reused row in the wrong direction. Going right to left, the left neighbour still holds the old row's value instead of the new one.
• Forgetting even-length centres for palindromes. "abba" has no middle letter; its centre is the gap between the two b's.
• Using a greedy rule on a grid or on Interleaving String. Taking the cheaper step, or the first string whose letter matches, can lead to a dead end that only the full table reveals.