One table, two inputs

The most reusable two-dimensional state in the course: how much of each input has been consumed.

Why it works

The transition splits on whether the ends match

Look at the last character of each consumed prefix. If they match, that pair can be used together and the problem reduces to (i-1, j-1) plus whatever using them is worth.

If they do not match, one of them must be given up, and you take the better of dropping the last character of the first input or of the second: (i-1, j) or (i, j-1).

Almost every problem in this family is that shape with a different notion of what using a matching pair is worth.

Below, two cells are filled from neighbors that are already known, one where the ends match and one where they do not.

1a, b = "abcde", "ace"2 3# best[i][j] covers the first i of a and the first j of b. Rows 0 to 2 are done.4best = [[0, 0, 0, 0],5        [0, 1, 1, 1],6        [0, 1, 1, 1],7        [0, 0, 0, 0]]8 9i = 3                                  # filling the row for 'c'10for j in (1, 2, 3):11    if a[i - 1] == b[j - 1]:12        best[i][j] = best[i - 1][j - 1] + 113        why = "match, so the diagonal plus one"14    else:15        best[i][j] = max(best[i - 1][j], best[i][j - 1])16        why = "mismatch, so the better of up and left"17    print(a[i - 1], "vs", b[j - 1], "->", best[i][j], "(" + why + ")")

A match reaches diagonally. A mismatch reaches up and left and takes the better of the two.

Trace it· 8 min

Fill part of the table

Build the shared-sequence table for a = "abc" and b = "ac". Table index i means the first i characters of a, and j means the first j of b. Fill in the row for i = 3, that is the whole of abc.

cell	value
i=3, j=0
i=3, j=1
i=3, j=2

Problem· 25 min

Longest Common Subsequence

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1a, b = "abcde", "ace"2 3# best[i][j] covers the first i of a and the first j of b. Rows 0 to 2 are done.4best = [[0, 0, 0, 0],5 [0, 1, 1, 1],6 [0, 1, 1, 1],7 [0, 0, 0, 0]]8 9i = 3 # filling the row for 'c'10for j in (1, 2, 3):11 if a[i - 1] == b[j - 1]:12 best[i][j] = best[i - 1][j - 1] + 113 why = "match, so the diagonal plus one"14 else:15 best[i][j] = max(best[i - 1][j], best[i][j - 1])16 why = "mismatch, so the better of up and left"17 print(a[i - 1], "vs", b[j - 1], "->", best[i][j], "(" + why + ")")

cell

value

i=3, j=0

i=3, j=1

i=3, j=2