Longest shared subsequence of two strings

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
a, b = "abcde", "ace"
row = [0] * (len(b) + 1)
for x in a:
    nxt = [0]
    for j, y in enumerate(b, 1):
        same = x == y
        nxt.append(row[j - 1] + 1 if same else max(row[j], nxt[j - 1]))
    row = nxt
print(row)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [0, 1, 2, 3]

Right: all of 'ace' appears in order inside 'abcde'.

The last row tells you the best for each prefix of the shorter string, so the final cell is the full answer.

Why not the others?
  • B [0, 1, 1, 1]. Later letters c and e also match.
  • C [0, 1, 2, 2]. e is the last letter of both strings and matches.

30-second answer

Let best[i][j] be the answer for the first i letters of one string and the first j of the other. If the current letters match, best[i][j] = best[i - 1][j - 1] + 1; otherwise take the larger of dropping one letter from either side. O(m × n) time; two rows give O(n) memory.

Practise saying it · 60 s. No recording, just a timer

Explain the longest shared subsequence table.

Say your answer out loud, then check which of these points you covered:

  • best over prefixes
  • Match: diagonal + 1; else max
  • O(m × n)

Deep dive

This is the 'longest common subsequence' table, the basis of line-based diff tools.

Same table shape as the fewest-edits question, with max instead of min.

Walk back from the last cell to recover the shared letters.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def shared_subseq(a: str, b: str) -> int:
    above = [0] * (len(b) + 1)  # previous row of the table
    for x in a:
        here = [0]
        for j, y in enumerate(b, 1):
            if x == y:
                here.append(above[j - 1] + 1)  # extend the match
            else:
                here.append(max(above[j], here[j - 1]))
        above = here
    return above[-1]

Common mistakes

  • Confusing it with the longest shared substring, which must be contiguous.
  • Taking the diagonal when letters differ.

Senior take & follow-ups

Say the subsequence-versus-substring difference before you start.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do diff tools use it?

    Show hint

    Lines in the shared subsequence are unchanged; the rest are insertions or deletions.

  2. What about the longest shared substring?

    Show hint

    Reset the cell to 0 when letters differ and track the maximum: still O(m × n).

Similar on iOS: A 50,000-item list that stutters on updates The iOS page applies many row changes to a list view efficiently; this page builds the shared-subsequence table that list diffing is based on.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.