Longest Common Subsequence

Build a table indexed by the two positions in the strings. If the two characters match, the answer for that cell is one more than the cell diagonally above and to the left. If they do not match, the answer is the larger of the two neighbouring cells, because at least one of the two strings has to skip a character.

def lcs_length(a, b):
    rows, cols = len(a), len(b)
    table = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            if a[i - 1] == b[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    return table[rows][cols]


print(lcs_length("abcde", "ace"))
print(lcs_length("abc", "abc"))

The outputs are 3 and 3. The longest common subsequence of abcde and ace is ace, and the two identical strings share their whole length.

The mechanism is the two cases. When the characters match you can always extend the best common subsequence of the shorter prefixes by that character. When they do not match, no common subsequence can use both characters at those positions, so you have to drop one of them and take the better of the two possibilities.

The trade-off to name is the space, which is quadratic in the product of the two lengths, because every cell of the table is needed to compute the ones that follow. There is a well known optimisation that reduces the space to linear by keeping only two rows, but it costs the ability to reconstruct the subsequence, because reconstruction needs to look back at the whole table. The other point is the difference between a subsequence and a substring: a subsequence does not have to be contiguous, which is why the mismatch case has to consider both skipping directions.

Keep the whole table, then walk it backwards from the bottom right corner. If the two characters at the current position matched, take that character and step diagonally. Otherwise step to whichever neighbouring cell holds the larger value.

The reason the whole table has to be kept is that the walk moves in three directions: up, left and diagonally. A rolling two row version would have thrown away the rows you still need to consult.

The mechanism is that the table records the answer for every pair of prefixes, so the walk always has a cell to move to and the length of the reconstructed subsequence matches the value in the corner cell. Because the walk moves from larger prefixes to smaller ones, it terminates at row zero or column zero where the remaining length is zero.

The trade-off to name is the space, which is quadratic in the product of the two lengths, and it is the price of the answer. If you only need the length, the two row version is strictly better and it is worth saying so in an interview, because it shows you understand which part of the algorithm needs the history. The other point is the tie breaking: when both neighbours hold the same value you can step either way and get a different but equally long subsequence, so the answer is not unique and the choice has to be stated.