On this page

Sequence DP

You have a list of numbers and want the longest run you can pick out, left to right, where every pick is bigger than the last. You have two versions of a file and want to know which lines were kept. You have a typo, kitten, and want to know how far it is from the word sitting. You have two strands of DNA and want to line them up so that as many letters as possible agree.

These are all sequence DP problems. The input is one or two sequences (arrays or strings), the answer is about subsequences (elements you keep, in order, possibly with gaps), and the DP state is "how far into each sequence am I". Three problems form the backbone of the whole family:

  • LIS (longest increasing subsequence): one sequence, state = "the subsequence ends at position ". by DP, with a clever array called tails and binary search.
  • LCS (longest common subsequence): two sequences, state = "prefixes of length and ", a 2-D table that you can draw and walk back through.
  • Edit distance (Levenshtein distance): the same 2-D table, but counting the cheapest way to turn one string into the other with insertions, deletions and substitutions.

Almost every other problem in this lesson is one of these three wearing a costume: longest palindromic subsequence is LCS against the reversed string, shortest common supersequence is LCS read the other way, Russian doll envelopes is LIS after a careful sort, and "delete-only edit distance" is a one-line formula on top of LCS.

This lesson assumes DP Foundations (state, transition, base case, memoization vs tabulation) and 1-D DP. The two-string table you meet here is stretched much further (wildcards, regex, word break, distinct subsequences, interleaving) in String DP, which is the natural next lesson; this page does not repeat those problems.

Why this exists

Comparing sequences is one of the oldest jobs computers were given. In 1965 Vladimir Levenshtein defined the distance that now carries his name, for error-correcting codes. In 1970 Needleman and Wunsch published a DP for aligning protein sequences, and in 1974 Wagner and Fischer published the edit-distance table you will fill below ("The String-to-String Correction Problem", JACM). Unix diff (Hunt and McIlroy, 1976) was built on longest common subsequence, and git diff today runs Myers' 1986 algorithm, which is a faster search over the very same edit graph.

LIS has its own history: the card game patience (solitaire) gives an algorithm, which Aldous and Diaconis surveyed in their 1999 paper "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem". A random permutation of numbers has an LIS of about (Vershik–Kerov and Logan–Shepp, 1977), which is why LIS shows up in probability as well as in interviews.

Why DP? Because a sequence of length has subsequences. Checking them all is hopeless past . But the question "what is the best subsequence that ends here?" or "what is the answer for these two prefixes?" has only or different versions, and each one is built from smaller ones. That is the DP signal.

Pattern triggers

If the problem says or has…Think of…
"longest increasing / non-decreasing subsequence", "longest chain", "longest sorted subset in original order"LIS: DP, or tails + binary search in
"minimum number of elements to delete so the array is sorted" (non-decreasing if equal values may stay)
"how many longest increasing subsequences"LIS DP with a second array of counts
"nest boxes / envelopes / dolls", "stack people by height and weight"Sort by one key, LIS on the other (with a tie-break trick)
"longest common subsequence", "keep the most lines", "uncrossed lines"LCS table dp[i][j] over prefixes
"minimum insertions / deletions / replacements to turn A into B"Edit distance (Levenshtein)
"only deletions allowed (from both)"
"costs differ by operation", "delete costs the ASCII value"Weighted edit distance, same table
"swapping two adjacent letters counts as one typo"Damerau–Levenshtein (one extra case)
"longest palindromic subsequence", "minimum insertions to make a palindrome"LCS with the reversed string, or interval DP on dp[i][j]
"shortest string that contains both as subsequences"Shortest common supersequence:
"longest common substring / repeated subarray" (contiguous)Different table: reset to 0 on a mismatch
"one sequence is a permutation of the other"LCS becomes LIS:

The meta-trigger: the problem talks about subsequences (order kept, gaps allowed) and asks for a longest, shortest, cheapest or count. If it says substring or subarray (no gaps), the table changes; see section 8 of the mechanics below.

Intuition & first principles

Subsequence, substring, and why the difference matters

A subsequence of ABCDE is anything you get by deleting some letters and keeping the rest in order: ACE, BD, ABCDE, and the empty string are all subsequences. CA is not (the order is wrong). A substring (or subarray, for numbers) must be contiguous: BCD is a substring, ACE is not.

There are subsequences of a length- string but only non-empty substrings. That is why substring problems can often be brute-forced in or , while subsequence problems need DP.

The "last element" question for one sequence

Take a = [3, 1, 4, 1, 5, 9, 2, 6]. Ask: what is the longest increasing subsequence that ends exactly at position ?

  • It ends at a[i]. The element before it (if any) is some a[j] with and a[j] < a[i].
  • Whatever came before a[j] is an increasing subsequence ending at , and we want it as long as possible.

So L[i] = 1 + max(L[j] for j < i with a[j] < a[i]), or 1 if no such exists. This is a 1-D DP where each cell reads all cells to its left. The overall answer is the largest L[i], because the LIS has to end somewhere.

The "last letters" question for two sequences

Take two strings A = ABCBDAB and B = BDCABA. Look at the last letter of each prefix you are comparing, A[i-1] and B[j-1]:

  • They are equal. Then some optimal common subsequence uses this pair as its last letter (if it used some earlier copy, you could swap to this one without loss). Answer: 1 + LCS(first i-1 letters, first j-1 letters).
  • They differ. They cannot both be the last letter of the common subsequence, so at least one of them is unused. Throw away the last letter of A or of B, whichever leaves the better answer: max(LCS(i-1, j), LCS(i, j-1)).

That is the entire LCS recurrence. Edit distance asks the same question with a different answer: if the letters are equal, it costs nothing to match them; if they differ, either substitute one for the other, delete from A, or insert into A, each costing 1, and take the cheapest.

A tiny example you can hold in your head

LCS of AB and BA. The common subsequences are the empty string, A, and B. AB is not common (in BA, A comes after B). So the LCS has length 1. The table:

        ε   B   A
   ε    0   0   0
   A    0   0   1
   B    0   1   1

Cell (A, BA): last letters A and A match, so 1 + (ε, B) = 1. Cell (AB, B): B and B match, so 1 + (A, ε) = 1. Cell (AB, BA): B vs A differ, so max(up = 1, left = 1) = 1.

Which cells does a cell read?

graph LR
    D["dp[i-1][j-1] diagonal"] -->|"letters match: +1 or +0"| C["dp[i][j]"]
    U["dp[i-1][j] up"] -->|"drop A's last letter"| C
    L["dp[i][j-1] left"] -->|"drop B's last letter"| C

Every two-sequence DP in this lesson reads the same three neighbours: up, left, and up-left diagonal. Row-major order (row by row, left to right) fills all three before the current cell. This is the same picture as Grid DP, with the moves "skip a letter of A" (down), "skip a letter of B" (right) and "use both letters" (diagonal).

The four questions for every sequence DP

  1. What does one cell mean? "Best subsequence ending at " (LIS) or "answer for prefixes A[:i], B[:j]" (LCS, edit distance).
  2. What decision happens at the last element? Which earlier element precedes it (LIS); match / skip one / skip the other (LCS); match / substitute / insert / delete (edit distance).
  3. What are the base cases? An empty prefix: LCS with an empty string is 0; edit distance from an empty string to B[:j] is (insert everything).
  4. How do you get the actual subsequence back, not just its length? Walk back from the answer cell, re-asking which option produced each value.

Mechanics

1. LIS in O(n²)

State: L[i] = length of the longest strictly increasing subsequence that ends at index . Transition: L[i] = 1 + max(L[j]) over with a[j] < a[i] (or 1 if none). Answer: max(L). Reconstruction: store prev[i] = the that won; follow prev from the best .

Dry run on a = [3, 1, 4, 1, 5, 9, 2, 6]:

ia[i]Smaller earlier values (index: L)L[i]prev[i]
03none1—
11none1—
240:1, 1:120
31none (1 is not < 1)1—
450:1, 1:1, 2:2, 3:132
59everything before: best is 4:344
621:1, 3:121
760:1, 1:1, 2:2, 3:1, 4:3, 6:244

The maximum is 4, reached at index 5 (... 5, 9) and index 7 (... 5, 6). Following prev from 5: 5 → 4 → 2 → 0 gives 3, 4, 5, 9. Time : each of the cells scans everything to its left. Fine for a few thousand.

def lis_quadratic(a):
    n = len(a)
    L, prev = [1] * n, [-1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and L[j] + 1 > L[i]:
                L[i], prev[i] = L[j] + 1, j
    if n == 0:
        return []
    i = max(range(n), key=lambda k: L[k])       # first index with the largest L
    out = []
    while i != -1:
        out.append(a[i])
        i = prev[i]
    return out[::-1]


assert lis_quadratic([3, 1, 4, 1, 5, 9, 2, 6]) == [3, 4, 5, 9]
assert lis_quadratic([10, 9, 2, 5, 3, 7, 101, 18]) == [2, 5, 7, 101]
assert lis_quadratic([]) == []

2. LIS in O(n log n): patience sorting and the tails array

The quadratic DP asks, for every new element, "which earlier subsequence can I extend?" and scans all of them. The fast method keeps a much smaller summary.

The key idea. For each length , among all increasing subsequences of length seen so far, we only care about the one with the smallest last element. A smaller ending is never worse: anything that could extend a subsequence ending in 7 can also extend one ending in 5. Call that smallest ending tails[k-1] (0-based, so tails[0] is the best ending for length 1).

The update. For a new element x:

  1. Find the first position p where tails[p] >= x (that is lower_bound, Python's bisect_left).
  2. If there is no such position, x is bigger than every tail: it extends the longest subsequence. Append it.
  3. Otherwise set tails[p] = x: x ends a length- subsequence with a smaller (or equal) ending than before.

The answer is len(tails).

The name comes from the card game. Deal cards one at a time onto piles; a card may only go on a pile whose top card is larger, and you always choose the leftmost such pile, starting a new pile on the right if none fits. The pile tops, left to right, are exactly tails, and the number of piles is the LIS length.

Dry run on a = [3, 1, 4, 1, 5, 9, 2, 6]:

StepxBinary search in tailspActiontails after
13empty0append[3]
213 ≥ 1 at index 00replace 3[1]
34nothing ≥ 41append[1, 4]
411 ≥ 1 at index 00replace 1 (no change)[1, 4]
55nothing ≥ 52append[1, 4, 5]
69nothing ≥ 93append[1, 4, 5, 9]
724 ≥ 2 at index 11replace 4[1, 2, 5, 9]
869 ≥ 6 at index 33replace 9[1, 2, 5, 6]

len(tails) = 4. Correct.

`tails` is not the LIS

The final tails = [1, 2, 5, 6] is not a subsequence of the input: the 2 is at index 6, after the 5 at index 4. tails is a summary ("for each length, the best ending seen so far"), mixing endings from different subsequences. Its length is right; its contents are not an answer. To get a real LIS you need the reconstruction below.

Each card goes on the leftmost pile whose top is ≥ it — a binary search over the pile tops — and the number of piles is the LIS length.

Reconstruction. Alongside tails, keep:

  • tails_idx[k] = the input index of the element currently stored in tails[k];
  • parent[i] = when element was placed at position , the index stored in tails_idx[p-1] at that moment (or if ).

When a[i] lands at position , tails_idx[p-1] is some earlier index whose value is smaller than a[i] and which ends a length- subsequence. So parent[i] is a valid predecessor, and following parents from tails_idx[last] walks back through a genuine increasing subsequence of the full length.

On the example: when 6 (index 7) lands at , tails_idx[2] points at index 4 (the 5). When 5 landed at , tails_idx[1] pointed at index 2 (the 4). When 4 landed at , tails_idx[0] pointed at index 1 (the first 1). So the walk is 7 → 4 → 2 → 1, giving 1, 4, 5, 6 — a real increasing subsequence of length 4. Note it uses the first 1, not the second: when index 3 replaced tails[0], the 4 had already recorded its parent.

flowchart LR
    X["next element x"] --> BS["p = first index with tails[p] >= x"]
    BS -->|"p == len(tails)"| AP["append x, record parent = tails_idx[p-1]"]
    BS -->|"p < len(tails)"| RP["tails[p] = x, record parent = tails_idx[p-1]"]
    AP --> N["next element"]
    RP --> N

Strict vs non-strict. For a non-decreasing subsequence (equal values allowed), use upper_bound (bisect_right): the first tail strictly greater than x. With bisect_left, a second 1 replaces the first; with bisect_right, it is appended after it. This one-character difference is the most common LIS bug.

3. Number of longest increasing subsequences

Keep two arrays in the quadratic DP: L[i] (length of the longest IS ending at ) and C[i] (how many IS of that length end at ). For each with a[j] < a[i]:

  • if L[j] + 1 > L[i]: a new best. L[i] = L[j] + 1, C[i] = C[j];
  • if L[j] + 1 == L[i]: another way to reach the same best. C[i] += C[j].

Answer: sum of C[i] over all with L[i] = max(L).

ia[i]LCWhere the count comes from
0311itself
1111itself
2422from 3 (i=0) and from 1 (i=1)
3111itself
4532from 4 (i=2), which has 2
5942from 5 (i=4)
6222from 1 (i=1) and from 1 (i=3)
7642from 5 (i=4)

Length 4 is reached at indices 5 and 7, each with count 2: 4 longest increasing subsequences (3 4 5 9, 1 4 5 9, 3 4 5 6, 1 4 5 6). The two 1s count as different subsequences because they sit at different positions.

def count_lis(a):
    n = len(a)
    if n == 0:
        return 0
    L, C = [1] * n, [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                if L[j] + 1 > L[i]:
                    L[i], C[i] = L[j] + 1, C[j]
                elif L[j] + 1 == L[i]:
                    C[i] += C[j]
    best = max(L)
    return sum(c for l, c in zip(L, C) if l == best)


assert count_lis([3, 1, 4, 1, 5, 9, 2, 6]) == 4
assert count_lis([1, 3, 5, 4, 7]) == 2
assert count_lis([2, 2, 2, 2, 2]) == 5

. An version replaces the inner scan with a Fenwick tree or segment tree indexed by (compressed) value, where each node stores a pair (best length, count) and the merge adds counts on equal lengths.

4. Russian doll envelopes: LIS in two dimensions

Envelopes have a width and a height. One fits inside another only if it is strictly smaller in both. What is the longest chain of nested envelopes?

Step 1: sort by width. Now any chain must go left to right in the sorted list, and the question becomes: the longest subsequence whose widths and heights both strictly increase.

Step 2: break ties by height, descending. Envelopes with equal width can never nest. If we sorted ties by ascending height, (6,4), (6,7) would look like an increasing height pair and the LIS would wrongly chain them. Sorting equal widths by descending height makes their heights a decreasing run, so a strictly increasing subsequence can take at most one of them.

Step 3: LIS (strict) on heights, in .

Example: [[5,4], [6,4], [6,7], [2,3]] sorts to (2,3), (5,4), (6,7), (6,4). Heights 3, 4, 7, 4; LIS = 3, 4, 7 → 3 envelopes: (2,3) ⊂ (5,4) ⊂ (6,7).

from bisect import bisect_left


def max_envelopes(env):
    env = sorted(env, key=lambda e: (e[0], -e[1]))   # width up, height down on ties
    tails = []
    for _, h in env:
        p = bisect_left(tails, h)                     # strict LIS on heights
        if p == len(tails):
            tails.append(h)
        else:
            tails[p] = h
    return len(tails)


assert max_envelopes([[5, 4], [6, 4], [6, 7], [2, 3]]) == 3
assert max_envelopes([[1, 1], [1, 1], [1, 1]]) == 1
assert max_envelopes([[4, 5], [4, 6], [6, 7], [2, 3], [1, 1]]) == 4

In three or more dimensions the trick stops working (you can sort by one key, but the rest is a partial order) and you fall back to the DP, or to the DAG DP view of "longest path in a comparability graph".

5. LCS: the table and the walk back

State: dp[i][j] = LCS length of A[:i] and B[:j] (the first letters of A and the first of B). Base: dp[0][j] = dp[i][0] = 0. Transition:

Answer: dp[m][n].

The CLRS example (§14.4), A = ABCBDAB, B = BDCABA:

          ε   B   D   C   A   B   A
     ε    0   0   0   0   0   0   0
     A    0   0   0   0   1   1   1
     B    0   1   1   1   1   2   2
     C    0   1   1   2   2   2   2
     B    0   1   1   2   2   3   3
     D    0   1   2   2   2   3   3
     A    0   1   2   2   3   3   4
     B    0   1   2   2   3   4   4

A few cells by hand:

CellLettersRuleValue
(1,4) A vs BDCAA = Adiagonal (0,3) = 0, plus 11
(2,1) AB vs BB = Bdiagonal (1,0) = 0, plus 11
(3,3) ABC vs BDCC = Cdiagonal (2,2) = 1, plus 12
(4,5) ABCB vs BDCABB = Bdiagonal (3,4) = 2, plus 13
(5,6) ABCBD vs BDCABAD ≠ Amax(up (4,6) = 3, left (5,5) = 3)3
(6,6) ABCBDA vs BDCABAA = Adiagonal (5,5) = 3, plus 14
(7,6) whole stringsB ≠ Amax(up (6,6) = 4, left (7,5) = 4)4

Walking back. Start at (m, n) = (7, 6):

  • If the letters at (i, j) match, that letter is part of the LCS: record it and step diagonally to (i-1, j-1).
  • Otherwise step to whichever of up and left holds the larger value (on a tie, pick one consistently; this code prefers up).

From (7,6): B ≠ A, up (6,6) = 4 ≥ left (7,5) = 4 → up. (6,6): A = A, record A, go to (5,5). (5,5): D ≠ B, up (4,5) = 3 > left (5,4) = 2 → (4,5). (4,5): B = B, record B, go to (3,4). (3,4): C ≠ A, up 1 < left 2 → (3,3). (3,3): C = C, record C, (2,2). (2,2): B ≠ D, up 0 < left 1 → (2,1). (2,1): B = B, record B, (1,0). Stop. Reversed: BCBA, length 4. (BDAB and BCAB are other LCSs; the tie-breaking rule picks which one you get.)

Hirschberg's linear-space trick. The full table costs memory: for two 100,000-line files, that is cells. If you only need the length, keep two rows ( memory). If you need the actual subsequence in linear space, Hirschberg (1975) splits A in half, runs the two-row DP forwards on the top half and backwards on the bottom half to find the column where an optimal path crosses the middle row, then recurses on the two halves. Total time stays (the work halves at each level: ), memory drops to . Kleinberg & Tardos §6.7 has a clear proof.

6. Edit distance and its variants

Edit distance (Levenshtein distance) between A and B is the smallest number of single-character edits that turn A into B, where an edit is:

  • insert a character,
  • delete a character, or
  • substitute (replace) one character by another.

State: dp[i][j] = edit distance between A[:i] and B[:j]. Base: dp[i][0] = i (delete all letters), dp[0][j] = j (insert all letters). Transition:

The three options in the min, in plain words, for the last letters:

  • diagonal dp[i-1][j-1] + 1: substitute A[i-1] by B[j-1], then fix the rest;
  • up dp[i-1][j] + 1: delete A[i-1], then turn A[:i-1] into B[:j];
  • left dp[i][j-1] + 1: turn A[:i] into B[:j-1], then insert B[j-1].

(When the letters are equal, taking the free diagonal is always at least as good as the other two; you can include all three in the min for safety and get the same answer.)

kitten → sitting:

          ε   s   i   t   t   i   n   g
     ε    0   1   2   3   4   5   6   7
     k    1   1   2   3   4   5   6   7
     i    2   2   1   2   3   4   5   6
     t    3   3   2   1   2   3   4   5
     t    4   4   3   2   1   2   3   4
     e    5   5   4   3   2   2   3   4
     n    6   6   5   4   3   3   2   3

Distance 3. Selected cells:

CellLettersRuleValue
(1,1) k vs sdiffer1 + min(diag 0, up 1, left 1)1
(2,2) ki vs sii = icopy diagonal (1,1)1
(4,4) kitt vs sittt = tcopy diagonal (3,3)1
(5,5) kitte vs sittie ≠ i1 + min(diag 1, up 2, left 2)2
(6,6) kitten vs sittinn = ncopy diagonal (5,5)2
(6,7) kitten vs sittingn ≠ g1 + min(diag 3, up 4, left 2)3

Walking back from (6,7): left (insert g) → (6,6) diagonal match n → (5,5) diagonal, substitute e→i → (4,4), (3,3), (2,2) matches → (1,1) substitute k→s. The script: substitute k→s, substitute e→i, insert g.

Each cell is a free diagonal copy on a match, else 1 + the min of its three neighbours; walking back from the corner reads off the edit script.

Variants you can solve by changing one line:

  • Insert/delete only (no substitution; LeetCode 583). A substitution is now a delete plus an insert. Every letter not in the LCS of the two strings must be deleted from A or inserted from B, so the answer is . For kitten/sitting: LCS = 4 (ittn), answer . Equivalently, set the substitution cost to 2 in the table.
  • Weighted edit distance. Give each operation its own cost: ins(c), del(c), sub(c, d). The recurrence is unchanged except the +1s become those costs. "Minimum ASCII delete sum" (LeetCode 712) is the delete-only version with del(c) = ord(c). In biology, substitution costs come from a matrix such as BLOSUM62, and gaps cost more to open than to extend (affine gaps; Gotoh, 1982, uses three tables instead of one).
  • Damerau–Levenshtein. Damerau (1964) reported that over 80% of misspellings in his sample were a single insertion, deletion, substitution, or transposition of two adjacent letters (teh → the). Adding one case gives the optimal string alignment (OSA) distance: if A[i-1] = B[j-2] and A[i-2] = B[j-1], also consider dp[i-2][j-2] + 1. Caveat: OSA forbids editing a substring more than once, so it is not a true metric: OSA(ca, abc) = 3, while the unrestricted Damerau–Levenshtein distance (Lowrance & Wagner, 1975), which needs an extra per-letter table, is 2 (ca → ac → abc).

7. Longest palindromic subsequence and shortest common supersequence

Longest palindromic subsequence (LPS). A palindrome reads the same backwards. The LPS of s has the same length as the LCS of s and reverse(s): a palindromic subsequence of s is also a subsequence of reverse(s), which gives LPS ≤ LCS, and a matching argument on the two copies gives the other direction. For bbbab, LCS with babbb is 4 (bbbb).

The LCS string itself might not be a palindrome

The length is right, but a particular LCS of s and reverse(s) need not be a palindrome. For s = acbac, reverse(s) = cabca, and abc is a common subsequence of length 3 (the LPS length), yet abc is not a palindrome. If you need the palindrome itself, use the interval form below and walk back through it.

The interval form works on one string directly. dp[i][j] = LPS length of s[i..j] (inclusive):

  • dp[i][i] = 1;
  • if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 (both ends join the palindrome);
  • else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (drop one end).

Fill from right to left so dp[i+1][...] is ready. This is the first example of Interval DP, where the state is a contiguous range and short ranges are solved before long ones. A useful corollary: the minimum number of insertions that make s a palindrome is len(s) - LPS(s) (LeetCode 1312).

def lps_interval(s):
    n = len(s)
    if n == 0:
        return ""
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2      # inner part is 0 when j == i + 1
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    left, right, i, j = [], [], 0, n - 1           # walk back, building both halves
    while i <= j:
        if i == j:
            left.append(s[i])
            break
        if s[i] == s[j]:
            left.append(s[i]); right.append(s[j]); i += 1; j -= 1
        elif dp[i + 1][j] >= dp[i][j - 1]:
            i += 1
        else:
            j -= 1
    return "".join(left) + "".join(reversed(right))


assert lps_interval("bbbab") == "bbbb"
assert lps_interval("BBABCBCAB") == "BACBCAB"     # length 7; BABCBAB is another answer
p = lps_interval("acbac")
assert len(p) == 3 and p == p[::-1]

Shortest common supersequence (SCS). The shortest string that has both A and B as subsequences. Every letter of the LCS can be shared; every other letter must appear on its own. So . To build it, walk back through the LCS table: on a match, emit the letter once and move diagonally; on a mismatch, emit the letter of the string you are dropping and move in that direction; when one string runs out, emit the rest of the other.

def shortest_common_supersequence(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
    out, i, j = [], m, n
    while i and j:
        if a[i-1] == b[j-1]:
            out.append(a[i-1]); i -= 1; j -= 1      # shared letter, emitted once
        elif dp[i-1][j] >= dp[i][j-1]:
            out.append(a[i-1]); i -= 1              # a's letter is not shared
        else:
            out.append(b[j-1]); j -= 1
    out.extend(reversed(a[:i]))                     # leftovers, then reverse everything
    out.extend(reversed(b[:j]))
    return "".join(reversed(out))


s = shortest_common_supersequence("abac", "cab")
assert s == "cabac" and len(s) == 4 + 3 - 2
s = shortest_common_supersequence("AGGTAB", "GXTXAYB")
assert len(s) == 6 + 7 - 4

8. Longest common substring vs subsequence

A common substring must be contiguous in both strings. The table changes in one place: on a mismatch, the run of matching letters is broken, so the cell resets to 0.

sub[i][j] = length of the longest common substring that ends exactly at A[i-1] and B[j-1]:

  • if A[i-1] == B[j-1]: sub[i][j] = sub[i-1][j-1] + 1;
  • else: sub[i][j] = 0.

The answer is the maximum over all cells, not the corner cell. For ABABC and BABCA, both the longest common substring and the LCS are BABC (length 4). For ABCBDAB and BDCABA, the LCS is 4 but the longest common substring is only 2 (AB, BD, or CA).

def longest_common_substring(a, b):
    best, end = 0, 0
    prev = [0] * (len(b) + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                cur[j] = prev[j-1] + 1
                if cur[j] > best:
                    best, end = cur[j], i
        prev = cur
    return a[end - best:end]


assert longest_common_substring("ABABC", "BABCA") == "BABC"
assert len(longest_common_substring("ABCBDAB", "BDCABA")) == 2

time. For long strings, a suffix automaton or suffix array gives or ; binary search plus rolling hashes gives expected. There is no comparable speed-up for LCS in general.

Longest common subsequenceLongest common substring
Gaps allowedyesno
Cell meaninganswer for prefixesrun ending exactly here
On mismatchmax(up, left)0
Answerdp[m][n]max over all cells
Faster algorithmsnone strongly subquadratic in generalsuffix structures,

How the family fits together

graph TD
    LCS["LCS table over prefixes"] --> ED["Edit distance: +1 costs, min"]
    LCS --> DEL["Delete-only distance = m + n - 2 LCS"]
    LCS --> SCS["Shortest common supersequence = m + n - LCS"]
    LCS --> LPS["Longest palindromic subsequence = LCS with reverse"]
    LCS --> SUB["Common substring: reset to 0 on mismatch"]
    ED --> W["Weighted and affine-gap alignment"]
    ED --> DL["Damerau: add transposition"]
    LIS["LIS ending at i"] --> FAST["tails + binary search O(n log n)"]
    LIS --> CNT["Count LIS: add a count array"]
    FAST --> ENV["Russian dolls: sort, then LIS"]
    LCS -.->|"permutations"| FAST

The dashed arrow: if B is a permutation of A (every element appears once in each), replace each element of A by its position in B. A common subsequence is then exactly an increasing subsequence of those positions, so LCS = LIS in . Hunt and Szymanski (1977) generalised this idea to arbitrary strings: their algorithm runs in where is the number of matching pairs, which is fast when few lines match, the common case in diff.

The ladder: brute force → better → optimal

LIS

RungMethodTimeSpaceWhy it is better than the rung above
1Try every subsequenceBaseline, obviously correct
2Memoized "longest from with last value "Each (position, last) pair solved once
3L[i] = best ending at One dimension fewer: the last value is a[i]
4tails + binary searchKeeps only the best ending per length, and that list is sorted

Rung 1 in code (useful as a test oracle for ):

from itertools import combinations


def lis_brute(a):
    for k in range(len(a), 0, -1):
        for idx in combinations(range(len(a)), k):
            if all(a[idx[t]] < a[idx[t + 1]] for t in range(k - 1)):
                return k
    return 0


assert lis_brute([3, 1, 4, 1, 5, 9, 2, 6]) == 4

Is optimal? In the comparison model, yes: Fredman (1975) showed comparisons are needed in the worst case. If values are small integers, van Emde Boas–style structures give , rarely worth it.

LCS and edit distance

RungMethodTimeSpaceWhy it is better
1Try every subsequence of the shorter string, test if it is a subsequence of the otherBaseline
2Plain recursion on (i, j) worst case stackSimple, still exponential
3Memoized recursion + stackOnly distinct subproblems
4TabulationNo recursion; table kept for reconstruction
5Two rolling rowsLength only
6HirschbergLinear space and reconstruction
sideMyers , Ukkonen's banded DPFast when the strings are similar (small distance )

Can we beat ? Masek and Paterson (1980) shaved a log factor with the "Four Russians" trick, . Backurs and Indyk (STOC 2015) proved that a strongly subquadratic algorithm () for edit distance would refute the Strong Exponential Time Hypothesis; Abboud, Backurs and Vassilevska Williams (2015) proved the same for LCS. So, under a widely believed conjecture, quadratic is essentially the truth, and practical speed-ups come from exploiting similarity (Myers, banding) or approximation.

Correctness

LIS quadratic DP. Induction on . Any increasing subsequence ending at is either just a[i] (length 1) or some increasing subsequence ending at a with a[j] < a[i], followed by a[i]. The best such has length L[j] + 1 by the induction hypothesis, and the max over picks the best. The overall LIS ends at some index, so max(L) is the answer.

LIS with tails. Define, after processing a prefix of the array, = the smallest possible last element of an increasing subsequence of length in that prefix (undefined if none exists). Claim: the algorithm's tails[k-1] equals for every length that exists, and len(tails) is the largest such .

  1. tails is strictly increasing. Take the subsequence of length that ends in . Drop its last element: you get a subsequence of length whose last element is smaller than . So . (This follows from the definition alone, so binary search is legal.)
  2. The update keeps the definition true. A new element can be the end of a length- subsequence exactly when some length- subsequence in the old prefix ends below , that is, when (or ). Let = number of tails smaller than (bisect_left). By sortedness, .
    • For lengths : could end them, but their current best endings are already , so nothing changes.
    • For length : can end one (because ), and , so the new best ending is . That is exactly tails[p] = x (or an append if was the full length).
    • For lengths : would need , which is false. Nothing changes.
  3. Length. A length- subsequence exists iff is defined iff len(tails).

Reconstruction. When a[i] is placed at position , tails_idx[p-1] is the index of an element that ends a length- subsequence and has value , and it appears before . By induction its own parent chain is an increasing subsequence of length , so appending gives one of length . Later replacements of tails_idx[p-1] do not affect parent[i], which was recorded at placement time.

LCS. Let be an LCS of A[:i] and B[:j].

  • If A[i-1] = B[j-1] = c: first, some LCS matches these two last letters with each other. If uses neither, appending makes it longer, a contradiction. If uses only one of them (say A[i-1], paired with an earlier B[t]), re-pair that final with B[j-1] instead; the letters of are unchanged. So assume ends with the pair. Removing it leaves a common subsequence of A[:i-1] and B[:j-1], and it must be a longest one, or swapping in a longer one would beat (cut and paste). So .
  • If they differ: cannot use both last letters as its final matched pair, so is a common subsequence of A[:i-1], B[:j] or of A[:i], B[:j-1]. Hence ; and both options are achievable, so equality holds.

This is CLRS Theorem 14.1.

Edit distance. Look at the last column of an optimal alignment (write A above B, inserting gap symbols - so both rows have equal length; each column is a match, a substitution, a deletion x/-, or an insertion -/y). The last column is one of: A[i-1] over B[j-1] (cost 0 or 1), A[i-1] over a gap (delete, cost 1), or a gap over B[j-1] (insert, cost 1). Removing that column leaves an optimal alignment of the corresponding shorter prefixes (cut and paste). The recurrence takes the min over exactly these three possibilities. The base cases align a prefix against an empty string, which needs one deletion or insertion per letter.

Why the free diagonal on a match is safe: one can show and (one extra letter changes the distance by at most one), so dp[i-1][j] + 1 ≥ dp[i-1][j-1] and likewise for left. Taking the diagonal when the letters match is never worse.

Shortest common supersequence. A common supersequence of A and B can be aligned so that each position of is used by A, by B, or by both; positions used by both form a common subsequence, so . The walk back constructs one of exactly that length.

Complexity

ProblemTimeSpaceNotes
LIS, quadraticsimple; easy to add counts or extra constraints
LIS, tailsoptimal in the comparison model
Number of LIS, or with a Fenwick treecounts can be huge: use big ints or a modulus
Russian dollssort + LIS
LCS / edit distance (full table)needed for simple reconstruction
LCS / edit distance (length only)two rows
Hirschberg reconstructionabout twice the time of one fill
LPS or via LCS with reverse or interval DP
SCSbuild from the LCS table
Longest common substring (DP)suffix automaton:

Best, average and worst cases are the same for the table methods: every cell is filled regardless of input. Myers' diff is the exception: where is the edit distance, so nearly identical files diff in nearly linear time, while totally different ones cost .

Real numbers: a edit-distance table is cells. In C++ that is roughly 0.1–0.3 s and 400 MB as 32-bit ints (so use two rows); in CPython, closer to a minute. This is why production diff tools do not fill the full table.

Implementation

Three programs, each in four languages, each with its own tests from this lesson: LIS in with reconstruction (strict and non-decreasing), LCS with reconstruction, and edit distance with the edit script. All were also checked against brute force on random small inputs.

LIS in O(n log n) with reconstruction

from bisect import bisect_left, bisect_right
from itertools import combinations
import random


def lis(a, strict=True):
    """Return one longest increasing subsequence of a (strict, or non-decreasing if strict=False)."""
    search = bisect_left if strict else bisect_right
    tails = []        # tails[k] = smallest last value of an increasing subsequence of length k+1
    tails_idx = []    # tails_idx[k] = index in a of that value
    parent = [-1] * len(a)
    for i, x in enumerate(a):
        p = search(tails, x)
        if p > 0:
            parent[i] = tails_idx[p - 1]     # predecessor recorded at placement time
        if p == len(tails):
            tails.append(x)
            tails_idx.append(i)
        else:
            tails[p] = x
            tails_idx[p] = i
    out = []
    i = tails_idx[-1] if tails_idx else -1
    while i != -1:
        out.append(a[i])
        i = parent[i]
    return out[::-1]


def is_increasing_subsequence(sub, a, strict=True):
    it = iter(a)
    in_order = all(any(x == y for y in it) for x in sub)
    ok = all(u < v if strict else u <= v for u, v in zip(sub, sub[1:]))
    return in_order and ok


if __name__ == "__main__":
    assert lis([3, 1, 4, 1, 5, 9, 2, 6]) == [1, 4, 5, 6]
    assert len(lis([10, 9, 2, 5, 3, 7, 101, 18])) == 4
    assert lis([]) == []
    assert lis([5, 5, 5]) == [5]
    assert lis([5, 5, 5], strict=False) == [5, 5, 5]
    assert lis([1, 3, 3, 2, 3], strict=False) == [1, 3, 3, 3]
    random.seed(7)
    for _ in range(300):                      # compare with brute force
        a = [random.randint(0, 6) for _ in range(random.randint(0, 9))]
        for strict in (True, False):
            best = 0
            for k in range(len(a) + 1):
                for idx in combinations(range(len(a)), k):
                    s = [a[t] for t in idx]
                    if all(u < v if strict else u <= v for u, v in zip(s, s[1:])):
                        best = k
            got = lis(a, strict)
            assert len(got) == best and is_increasing_subsequence(got, a, strict)
    print("LIS tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lis {
    /** First index p in tails[0..len) with tails[p] >= x (strict) or > x (non-strict). */
    static int search(int[] tails, int len, int x, boolean strict) {
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            boolean goRight = strict ? tails[mid] < x : tails[mid] <= x;
            if (goRight) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    static int[] lis(int[] a, boolean strict) {
        int n = a.length, len = 0;
        int[] tails = new int[n], tailsIdx = new int[n], parent = new int[n];
        for (int i = 0; i < n; i++) {
            int p = search(tails, len, a[i], strict);
            parent[i] = p > 0 ? tailsIdx[p - 1] : -1;
            tails[p] = a[i];
            tailsIdx[p] = i;
            if (p == len) len++;
        }
        int[] out = new int[len];
        int i = len > 0 ? tailsIdx[len - 1] : -1;
        for (int k = len - 1; k >= 0; k--) {
            out[k] = a[i];
            i = parent[i];
        }
        return out;
    }

    public static void main(String[] args) {
        check(Arrays.equals(lis(new int[]{3, 1, 4, 1, 5, 9, 2, 6}, true), new int[]{1, 4, 5, 6}));
        check(lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}, true).length == 4);
        check(lis(new int[]{}, true).length == 0);
        check(Arrays.equals(lis(new int[]{5, 5, 5}, true), new int[]{5}));
        check(Arrays.equals(lis(new int[]{5, 5, 5}, false), new int[]{5, 5, 5}));
        check(Arrays.equals(lis(new int[]{1, 3, 3, 2, 3}, false), new int[]{1, 3, 3, 3}));
        System.out.println("LIS tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

vector<int> lis(const vector<int>& a, bool strict = true) {
    vector<int> tails, tailsIdx, parent(a.size(), -1);
    for (int i = 0; i < (int)a.size(); i++) {
        auto it = strict ? lower_bound(tails.begin(), tails.end(), a[i])
                         : upper_bound(tails.begin(), tails.end(), a[i]);
        int p = int(it - tails.begin());
        if (p > 0) parent[i] = tailsIdx[p - 1];
        if (p == (int)tails.size()) {
            tails.push_back(a[i]);
            tailsIdx.push_back(i);
        } else {
            tails[p] = a[i];
            tailsIdx[p] = i;
        }
    }
    vector<int> out;
    for (int i = tailsIdx.empty() ? -1 : tailsIdx.back(); i != -1; i = parent[i]) out.push_back(a[i]);
    reverse(out.begin(), out.end());
    return out;
}

int main() {
    assert((lis({3, 1, 4, 1, 5, 9, 2, 6}) == vector<int>{1, 4, 5, 6}));
    assert(lis({10, 9, 2, 5, 3, 7, 101, 18}).size() == 4);
    assert(lis({}).empty());
    assert((lis({5, 5, 5}) == vector<int>{5}));
    assert((lis({5, 5, 5}, false) == vector<int>{5, 5, 5}));
    assert((lis({1, 3, 3, 2, 3}, false) == vector<int>{1, 3, 3, 3}));
    cout << "LIS tests passed\n";
    return 0;
}
function lis(a: number[], strict = true): number[] {
  const tails: number[] = [];
  const tailsIdx: number[] = [];
  const parent: number[] = new Array(a.length).fill(-1);
  for (let i = 0; i < a.length; i++) {
    let lo = 0, hi = tails.length; // first p with tails[p] >= a[i] (strict) or > a[i]
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      const goRight = strict ? tails[mid] < a[i] : tails[mid] <= a[i];
      if (goRight) lo = mid + 1;
      else hi = mid;
    }
    if (lo > 0) parent[i] = tailsIdx[lo - 1];
    tails[lo] = a[i];
    tailsIdx[lo] = i;
  }
  const out: number[] = [];
  for (let i = tailsIdx.length ? tailsIdx[tailsIdx.length - 1] : -1; i !== -1; i = parent[i]) out.push(a[i]);
  return out.reverse();
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const same = (x: number[], y: number[]): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(same(lis([3, 1, 4, 1, 5, 9, 2, 6]), [1, 4, 5, 6]));
assert(lis([10, 9, 2, 5, 3, 7, 101, 18]).length === 4);
assert(lis([]).length === 0);
assert(same(lis([5, 5, 5]), [5]));
assert(same(lis([5, 5, 5], false), [5, 5, 5]));
assert(same(lis([1, 3, 3, 2, 3], false), [1, 3, 3, 3]));
console.log("LIS tests passed");

In TypeScript, tails[lo] = a[i] with lo === tails.length appends, which is why there is no separate branch.

LCS with reconstruction

def lcs(a: str, b: str) -> str:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    out, i, j = [], m, n
    while i > 0 and j > 0:                      # walk back from the corner
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:      # tie: prefer up
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))


def lcs_length_two_rows(a: str, b: str) -> int:
    if len(b) > len(a):
        a, b = b, a                             # keep rows as short as possible
    prev = [0] * (len(b) + 1)
    for ch in a:
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            cur[j] = prev[j - 1] + 1 if ch == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


if __name__ == "__main__":
    assert lcs("ABCBDAB", "BDCABA") == "BCBA"
    assert lcs("abcde", "ace") == "ace"
    assert lcs("abc", "def") == ""
    assert lcs("", "abc") == ""
    assert lcs("kitten", "sitting") == "ittn"
    assert lcs_length_two_rows("ABCBDAB", "BDCABA") == 4
    assert lcs_length_two_rows("AB", "BA") == 1
    print("LCS tests passed")
public class Lcs {
    static String lcs(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        StringBuilder out = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                out.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) i--; // tie: prefer up
            else j--;
        }
        return out.reverse().toString();
    }

    static int lcsLengthTwoRows(String a, String b) {
        if (b.length() > a.length()) { String t = a; a = b; b = t; }
        int[] prev = new int[b.length() + 1], cur = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
            int[] t = prev; prev = cur; cur = t;
        }
        return prev[b.length()];
    }

    public static void main(String[] args) {
        check(lcs("ABCBDAB", "BDCABA").equals("BCBA"));
        check(lcs("abcde", "ace").equals("ace"));
        check(lcs("abc", "def").isEmpty());
        check(lcs("", "abc").isEmpty());
        check(lcs("kitten", "sitting").equals("ittn"));
        check(lcsLengthTwoRows("ABCBDAB", "BDCABA") == 4);
        check(lcsLengthTwoRows("AB", "BA") == 1);
        System.out.println("LCS tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string lcs(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
    string out;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) { out.push_back(a[i - 1]); i--; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) i--;   // tie: prefer up
        else j--;
    }
    reverse(out.begin(), out.end());
    return out;
}

int lcsLengthTwoRows(string a, string b) {
    if (b.size() > a.size()) swap(a, b);
    vector<int> prev(b.size() + 1, 0), cur(b.size() + 1, 0);
    for (char ch : a) {
        for (size_t j = 1; j <= b.size(); j++)
            cur[j] = ch == b[j - 1] ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    return prev[b.size()];
}

int main() {
    assert(lcs("ABCBDAB", "BDCABA") == "BCBA");
    assert(lcs("abcde", "ace") == "ace");
    assert(lcs("abc", "def").empty());
    assert(lcs("", "abc").empty());
    assert(lcs("kitten", "sitting") == "ittn");
    assert(lcsLengthTwoRows("ABCBDAB", "BDCABA") == 4);
    assert(lcsLengthTwoRows("AB", "BA") == 1);
    cout << "LCS tests passed\n";
    return 0;
}
function lcs(a: string, b: string): string {
  const m = a.length, n = b.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  const out: string[] = [];
  let i = m, j = n;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      out.push(a[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) i--; // tie: prefer up
    else j--;
  }
  return out.reverse().join("");
}

function lcsLengthTwoRows(a: string, b: string): number {
  if (b.length > a.length) [a, b] = [b, a];
  let prev = new Array<number>(b.length + 1).fill(0);
  let cur = new Array<number>(b.length + 1).fill(0);
  for (const ch of a) {
    for (let j = 1; j <= b.length; j++)
      cur[j] = ch === b[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
    [prev, cur] = [cur, prev];
  }
  return prev[b.length];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

assert(lcs("ABCBDAB", "BDCABA") === "BCBA");
assert(lcs("abcde", "ace") === "ace");
assert(lcs("abc", "def") === "");
assert(lcs("", "abc") === "");
assert(lcs("kitten", "sitting") === "ittn");
assert(lcsLengthTwoRows("ABCBDAB", "BDCABA") === 4);
assert(lcsLengthTwoRows("AB", "BA") === 1);
console.log("LCS tests passed");

Edit distance with the edit script

from typing import List, Tuple


def edit_distance(a: str, b: str) -> Tuple[int, List[str]]:
    """Levenshtein distance and one optimal script of edits turning a into b."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                              # delete everything
    for j in range(n + 1):
        dp[0][j] = j                              # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],   # substitute
                                   dp[i - 1][j],       # delete a[i-1]
                                   dp[i][j - 1])       # insert b[j-1]
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1] and dp[i][j] == dp[i - 1][j - 1]:
            i, j = i - 1, j - 1                   # match, no edit
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"substitute {a[i - 1]}->{b[j - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"delete {a[i - 1]}")
            i -= 1
        else:
            ops.append(f"insert {b[j - 1]}")
            j -= 1
    return dp[m][n], ops[::-1]


def edit_distance_two_rows(a: str, b: str) -> int:
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            same = a[i - 1] == b[j - 1]
            cur[j] = prev[j - 1] if same else 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


if __name__ == "__main__":
    d, ops = edit_distance("kitten", "sitting")
    assert d == 3
    assert ops == ["substitute k->s", "substitute e->i", "insert g"]
    assert edit_distance("horse", "ros")[0] == 3
    assert edit_distance("intention", "execution")[0] == 5
    assert edit_distance("", "abc") == (3, ["insert a", "insert b", "insert c"])
    assert edit_distance("abc", "") == (3, ["delete a", "delete b", "delete c"])
    assert edit_distance("same", "same") == (0, [])
    assert edit_distance_two_rows("kitten", "sitting") == 3
    assert edit_distance_two_rows("intention", "execution") == 5
    print("edit distance tests passed")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class EditDistance {
    /** Returns the distance; fills ops with one optimal edit script. */
    static int editDistance(String a, String b, List<String> ops) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1]
                        : 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
        ops.clear();
        int i = m, j = n;
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && a.charAt(i - 1) == b.charAt(j - 1) && dp[i][j] == dp[i - 1][j - 1]) {
                i--; j--;
            } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
                ops.add("substitute " + a.charAt(i - 1) + "->" + b.charAt(j - 1));
                i--; j--;
            } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
                ops.add("delete " + a.charAt(i - 1));
                i--;
            } else {
                ops.add("insert " + b.charAt(j - 1));
                j--;
            }
        }
        Collections.reverse(ops);
        return dp[m][n];
    }

    static int editDistanceTwoRows(String a, String b) {
        int n = b.length();
        int[] prev = new int[n + 1], cur = new int[n + 1];
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            cur[0] = i;
            for (int j = 1; j <= n; j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? prev[j - 1]
                        : 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
            int[] t = prev; prev = cur; cur = t;
        }
        return prev[n];
    }

    public static void main(String[] args) {
        List<String> ops = new ArrayList<>();
        check(editDistance("kitten", "sitting", ops) == 3);
        check(ops.equals(List.of("substitute k->s", "substitute e->i", "insert g")));
        check(editDistance("horse", "ros", ops) == 3);
        check(editDistance("intention", "execution", ops) == 5);
        check(editDistance("", "abc", ops) == 3 && ops.equals(List.of("insert a", "insert b", "insert c")));
        check(editDistance("abc", "", ops) == 3 && ops.equals(List.of("delete a", "delete b", "delete c")));
        check(editDistance("same", "same", ops) == 0 && ops.isEmpty());
        check(editDistanceTwoRows("kitten", "sitting") == 3);
        check(editDistanceTwoRows("intention", "execution") == 5);
        System.out.println("edit distance tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int editDistance(const string& a, const string& b, vector<string>& ops) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i - 1] == b[j - 1]
                           ? dp[i - 1][j - 1]
                           : 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
    ops.clear();
    int i = m, j = n;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i - 1] == b[j - 1] && dp[i][j] == dp[i - 1][j - 1]) {
            i--; j--;
        } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
            ops.push_back(string("substitute ") + a[i - 1] + "->" + b[j - 1]);
            i--; j--;
        } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
            ops.push_back(string("delete ") + a[i - 1]);
            i--;
        } else {
            ops.push_back(string("insert ") + b[j - 1]);
            j--;
        }
    }
    reverse(ops.begin(), ops.end());
    return dp[m][n];
}

int editDistanceTwoRows(const string& a, const string& b) {
    int n = b.size();
    vector<int> prev(n + 1), cur(n + 1);
    for (int j = 0; j <= n; j++) prev[j] = j;
    for (int i = 1; i <= (int)a.size(); i++) {
        cur[0] = i;
        for (int j = 1; j <= n; j++)
            cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] : 1 + min({prev[j - 1], prev[j], cur[j - 1]});
        swap(prev, cur);
    }
    return prev[n];
}

int main() {
    vector<string> ops;
    assert(editDistance("kitten", "sitting", ops) == 3);
    assert((ops == vector<string>{"substitute k->s", "substitute e->i", "insert g"}));
    assert(editDistance("horse", "ros", ops) == 3);
    assert(editDistance("intention", "execution", ops) == 5);
    assert(editDistance("", "abc", ops) == 3 && (ops == vector<string>{"insert a", "insert b", "insert c"}));
    assert(editDistance("abc", "", ops) == 3 && (ops == vector<string>{"delete a", "delete b", "delete c"}));
    assert(editDistance("same", "same", ops) == 0 && ops.empty());
    assert(editDistanceTwoRows("kitten", "sitting") == 3);
    assert(editDistanceTwoRows("intention", "execution") == 5);
    cout << "edit distance tests passed\n";
    return 0;
}
function editDistance(a: string, b: string): [number, string[]] {
  const m = a.length, n = b.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
  const ops: string[] = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && a[i - 1] === b[j - 1] && dp[i][j] === dp[i - 1][j - 1]) {
      i--; j--;
    } else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {
      ops.push(`substitute ${a[i - 1]}->${b[j - 1]}`);
      i--; j--;
    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
      ops.push(`delete ${a[i - 1]}`);
      i--;
    } else {
      ops.push(`insert ${b[j - 1]}`);
      j--;
    }
  }
  return [dp[m][n], ops.reverse()];
}

function editDistanceTwoRows(a: string, b: string): number {
  const n = b.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);
  let cur = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= a.length; i++) {
    cur[0] = i;
    for (let j = 1; j <= n; j++)
      cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1] : 1 + Math.min(prev[j - 1], prev[j], cur[j - 1]);
    [prev, cur] = [cur, prev];
  }
  return prev[n];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(eq(editDistance("kitten", "sitting"), [3, ["substitute k->s", "substitute e->i", "insert g"]]));
assert(editDistance("horse", "ros")[0] === 3);
assert(editDistance("intention", "execution")[0] === 5);
assert(eq(editDistance("", "abc"), [3, ["insert a", "insert b", "insert c"]]));
assert(eq(editDistance("abc", ""), [3, ["delete a", "delete b", "delete c"]]));
assert(eq(editDistance("same", "same"), [0, []]));
assert(editDistanceTwoRows("kitten", "sitting") === 3);
assert(editDistanceTwoRows("intention", "execution") === 5);
console.log("edit distance tests passed");

The walk back re-derives each step from the table instead of storing back-pointers. That works because every cell's value was produced by one of the three options, so at least one of the equality tests must succeed. Storing a direction byte per cell is the alternative when recomputing is awkward (weighted costs, affine gaps).

Real-world uses

  • diff, git diff and code review. A diff is an edit script between two lists of lines, and the "unchanged" lines form a common subsequence. The original Unix diff (Hunt and McIlroy, 1976) computed an LCS of the two files' lines with an algorithm closely related to Hunt–Szymanski. GNU diffutils and Git's default use Myers' algorithm (1986), which explores the same edit graph diagonal by diagonal and stops as soon as it reaches the end, so similar files are fast. Git also ships --patience (Bram Cohen's patience diff: find lines that occur exactly once in both files, take the LIS of their positions as anchors, recurse between anchors) and --histogram, plus --minimal to insist on a true minimum. The full story is in Git & Diff.
  • DNA and protein alignment. Needleman–Wunsch (1970) is global alignment: edit distance with scores instead of unit costs. Smith–Waterman (1981) is local alignment: the same table, but each cell may also restart at 0 (the "longest common substring" idea, with mismatches allowed). Gotoh (1982) added affine gap costs. Genome-scale tools such as BLAST (Altschul et al., 1990) use fast seed-and-extend heuristics and then run banded DP only around promising seeds, because the full table for two genomes is far too large.
  • Spell checkers and fuzzy search. Suggestions are dictionary words within a small edit distance of the typo. Peter Norvig's well-known corrector generates every string within distance 2. Lucene and Elasticsearch fuzzy queries compile a Levenshtein automaton (Schulz and Mihov, 2002) that accepts exactly the words within distance of the query and intersect it with the term dictionary; Lucene supports at most 2 edits. Damerau's transposition rule exists because swapped adjacent letters are the most common typo after the basic three.
  • Version control merges and three-way diff. diff3 and Git's merge machinery compute LCS-style alignments between base, ours and theirs.
  • Plagiarism and clone detection, file synchronisation, OCR post-correction, speech recognition scoring. Word error rate (WER), the standard metric for speech recognisers, is edit distance between word sequences divided by the reference length.
  • Scheduling and stacking (LIS). Box stacking, nesting, and "longest chain" questions in logistics are LIS on a sorted key. Patience sorting itself is a practical sort for nearly sorted data (few piles form).

Pitfalls & edge cases

  • Strict vs non-strict LIS. bisect_left for strictly increasing, bisect_right for non-decreasing. Test with [2, 2, 2]: strict gives 1, non-strict gives 3.
  • Returning tails as the LIS. Its length is right, its contents can be a non-subsequence ([1, 2, 5, 6] in this lesson).
  • Off-by-one between string index and table index. Table row refers to the letter A[i-1]. Most bugs in LCS code are a[i] where a[i-1] was meant.
  • Forgetting the base row and column of edit distance. dp[i][0] = i and dp[0][j] = j, not 0. With zeros you compute something else (a "free prefix" variant used for approximate substring search, which is a feature when you want it and a bug when you do not).
  • Common substring answer read from the corner. The answer is the maximum over all cells.
  • Russian dolls with equal widths. Without the descending-height tie-break, (6,4) and (6,7) chain illegally.
  • Counting LIS with duplicates. Equal values are never "increasing", so a[j] < a[i] must be strict; the two 1s in the example are different positions and count separately.
  • Count overflow. Counts of LIS can grow exponentially (an array like [2,1,4,3,6,5,...] doubles the count every pair); use 64-bit, big ints, or the problem's modulus.
  • Memory blow-up. A table does not fit in any RAM. Use two rows for the length, Hirschberg for reconstruction, or a banded/Myers approach when the strings are similar.
  • Unicode. "Edit distance between strings" depends on what a character is: bytes, UTF-16 code units, code points, or user-perceived graphemes (é can be one or two code points). Decide before comparing.
  • Recursion depth. Memoised LCS on two 5,000-letter strings recurses 10,000 deep. Python's default limit is 1,000. Tabulate.

Variations

  • Longest bitonic subsequence / mountain array. LIS ending at from the left plus LIS starting at from the right, minus one (LeetCode 1671 asks for the fewest removals).
  • Longest increasing subsequence with a gap limit, or with weights ("maximum sum increasing subsequence"): the quadratic DP adapts directly; the fast version uses a segment tree keyed by value.
  • Longest chain of pairs, longest string chain. Sort, then LIS or a greedy (pairs: sort by end and take greedily, like interval scheduling).
  • LCS of three strings. A 3-D table, . For strings the problem is NP-hard (Maier, 1978).
  • Uncrossed lines (LeetCode 1035) is LCS in disguise: lines between equal numbers that do not cross are a common subsequence.
  • Maximum dot product of two subsequences and other "pick from both, in order" scores: LCS-shaped tables with a different combine.
  • Local alignment (Smith–Waterman): max(0, …) in each cell, answer = max over cells.
  • Edit distance with a bound : only cells with can hold values , so fill a diagonal band of width : (Ukkonen, 1985).
  • Regex, wildcard, word break, distinct subsequences, interleaving: the same two-string table with different rules, all in String DP.
  • Palindromic substrings (contiguous) are interval DP or Manacher's linear-time algorithm (Palindromes & Manacher).

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Longest Increasing Subsequence (LeetCode 300) — Length of the longest strictly increasing subsequence. Teaches both the quadratic DP and tails.

Hint

bisect_left on tails; append or replace. The lis function above, returning len, is a full solution.

2. Longest Common Subsequence (LeetCode 1143) — Length of the LCS of two strings. Teaches the prefix table.

Hint

lcs_length_two_rows above.

3. Delete Operation for Two Strings (LeetCode 583) — Fewest single-letter deletions (from either string) to make them equal. Teaches the identity.

Hint

Everything outside an LCS must go.

4. Uncrossed Lines (LeetCode 1035) — Draw the most non-crossing lines between equal numbers in two rows. Teaches recognising LCS in disguise.

Hint

Non-crossing means the matched pairs appear in the same order in both rows.

5. Edit Distance (LeetCode 72) — Levenshtein distance between two words. Teaches the three-way min.

Hint

edit_distance_two_rows above.

6. Longest Palindromic Subsequence (LeetCode 516) — Teaches LCS-with-reverse and the interval form.

Solution
def longest_palindrome_subseq(s):
    n = len(s)
    dp = [0] * n                      # dp[j] holds LPS of s[i..j] for the current i
    for i in range(n - 1, -1, -1):
        prev_diag = 0                 # value of dp[i+1][j-1] before it is overwritten
        dp[i] = 1
        for j in range(i + 1, n):
            keep = dp[j]              # dp[i+1][j]
            dp[j] = prev_diag + 2 if s[i] == s[j] else max(dp[j], dp[j - 1])
            prev_diag = keep
    return dp[-1] if n else 0


assert longest_palindrome_subseq("bbbab") == 4
assert longest_palindrome_subseq("cbbd") == 2
assert longest_palindrome_subseq("a") == 1

One row of memory; prev_diag carries the old diagonal value, the same trick as in maximal square.

7. Minimum ASCII Delete Sum for Two Strings (LeetCode 712) — Cheapest deletions to equalise two strings, where deleting a letter costs its character code. Teaches weighted edit distance.

Hint

Base row/column are prefix sums of codes; mismatch = min(delete from a + up, delete from b + left).

8. Increasing Subsequence (CSES 1145) — LIS length for up to . Teaches that only the method passes.

Hint

tails with lower_bound.

9. LCS (AtCoder Educational DP Contest F) — Print one longest common subsequence. Teaches reconstruction.

Hint

The lcs function above. Strings up to 3000 letters: a int table is fine in C++/Java; in Python consider storing directions in a bytearray.

10. Number of Longest Increasing Subsequence (LeetCode 673) — Count the LIS. Teaches the length + count pair.

Solution

The count_lis function in section 3 is a full solution. In an interview, mention the Fenwick-tree version for large .

11. Russian Doll Envelopes (LeetCode 354) — Longest chain of nesting envelopes. Teaches the sort + tie-break + LIS trick.

Solution

max_envelopes in section 4. up to rules out the quadratic DP.

12. Shortest Common Supersequence (LeetCode 1092) — Build the shortest string containing both inputs as subsequences. Teaches reading the LCS table backwards to construct something else.

Solution

shortest_common_supersequence in section 7. Any valid shortest answer is accepted.

13. Maximum Length of Repeated Subarray (LeetCode 718) — Longest contiguous run common to two arrays. Teaches the reset-to-zero table.

Hint

longest_common_substring from section 8 works on lists too. Binary search + hashing is the follow-up.

14. Edit Distance (CSES 1639) — Levenshtein distance for strings up to 5000 letters. Teaches the two-row version under a time limit.

Hint

cells: fine in C++; in Python, two rows and local variables.

15. Minimum Number of Removals to Make Mountain Array (LeetCode 1671) — Remove the fewest elements so the array strictly rises then strictly falls. Teaches combining a left LIS and a right LIS.

Solution
from bisect import bisect_left


def lis_ending_at_each(a):
    tails, out = [], []
    for x in a:
        p = bisect_left(tails, x)
        if p == len(tails):
            tails.append(x)
        else:
            tails[p] = x
        out.append(p + 1)              # length of the best LIS ending exactly here
    return out


def minimum_mountain_removals(a):
    up = lis_ending_at_each(a)
    down = lis_ending_at_each(a[::-1])[::-1]
    best = max(u + d - 1 for u, d in zip(up, down) if u > 1 and d > 1)
    return len(a) - best


assert minimum_mountain_removals([1, 3, 1]) == 0
assert minimum_mountain_removals([2, 1, 1, 5, 6, 2, 3, 1]) == 3

The position p + 1 where an element lands in tails is exactly the LIS length ending at that element. The peak needs a real rise and a real fall (u > 1 and d > 1).

Common mistakes & interview follow-ups

"Why does binary search work on tails?" Because tails is strictly increasing: a length- subsequence minus its last element is a length- subsequence with a smaller ending. Say this in one sentence; interviewers want to hear it.

"Print the actual LIS, not just its length." Parent pointers recorded at placement time (this lesson's code). Mention that tails itself is not an answer.

"LCS in memory?" Two rows for the length. For the subsequence too: Hirschberg. Explain the middle-row split in two sentences.

"Your two strings are 1 GB log files that differ in a few lines." Not the DP table. Myers' or patience/histogram diff, possibly after hashing lines; mention that git does this.

"Edit distance with costs 1, 1, 2?" That is the delete/insert-only distance, , because a substitution costing 2 is never better than delete + insert.

"Is edit distance a metric?" Levenshtein, yes (symmetric, zero iff equal, triangle inequality). OSA (restricted Damerau), no: it fails the triangle inequality.

"Can you do better than ?" Not by much in general: Four Russians gives a log factor, and SETH-based lower bounds (Backurs–Indyk 2015) rule out . Mention banded DP if the distance is known to be small.

Mistakes interviewers watch for: a[i] vs a[i-1] index slips; base row/column of edit distance set to 0; strict/non-strict confusion; reading the common-substring answer from the corner; returning tails; forgetting the descending tie-break in envelopes.

Quick quiz

1. After processing [3, 1, 4, 1, 5, 9, 2], what is tails, and what is the LIS length?

Answer

[1, 2, 5, 9], length 4. The 2 replaced the 4.

2. Why is it safe to replace tails[p] with a smaller value?

Answer

tails[p] stands for "the best (smallest) ending of any length- subsequence seen so far". A smaller ending can be extended by everything the old one could, so we lose nothing; and the old subsequences still exist, they are just no longer the best representative.

3. What is the edit distance between horse and ros, and what is the delete/insert-only distance?

Answer

3 (e.g. substitute h→r, delete r, delete e). LCS(horse, ros) = 2 (os), so delete/insert-only is .

4. In the LCS table for ABCBDAB / BDCABA, cell (5,6) compares D with A. What does it read and what is its value?

Answer

They differ, so max(up (4,6) = 3, left (5,5) = 3) = 3.

5. What is the longest common substring of ABCBDAB and BDCABA, and why is the LCS longer?

Answer

Length 2 (AB, BD or CA). The LCS BCBA skips letters in between; a substring may not.

6. For Russian dolls, why sort equal widths by descending height?

Answer

So that among envelopes of the same width, heights decrease. A strictly increasing subsequence of heights can then pick at most one of them, which matches the rule that equal widths cannot nest.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., §14.4 (LCS, Theorem 14.1, the ABCBDAB/BDCABA example) and Problem 14-5 (edit distance).
  • Jon Kleinberg and Éva Tardos, Algorithm Design (2005), §6.6 (sequence alignment) and §6.7 (Hirschberg's linear-space alignment).
  • Robert A. Wagner and Michael J. Fischer, "The String-to-String Correction Problem", JACM 21(1), 1974.
  • Daniel S. Hirschberg, "A linear space algorithm for computing maximal common subsequences", CACM 18(6), 1975.
  • James W. Hunt and Thomas G. Szymanski, "A fast algorithm for computing longest common subsequences", CACM 20(5), 1977; J. W. Hunt and M. D. McIlroy, "An Algorithm for Differential File Comparison", Bell Labs CSTR #41, 1976.
  • Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica 1, 1986.
  • David Aldous and Persi Diaconis, "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem", Bulletin of the AMS 36(4), 1999.
  • Michael L. Fredman, "On computing the length of longest increasing subsequences", Discrete Mathematics 11(1), 1975.
  • Fred J. Damerau, "A technique for computer detection and correction of spelling errors", CACM 7(3), 1964.
  • Arturs Backurs and Piotr Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)", STOC 2015.
  • cp-algorithms, Longest increasing subsequence.
  • Git documentation, git diff --diff-algorithm (myers, minimal, patience, histogram).

Lessons: previous — Knapsack · next — String DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Binary Search · Grid DP · String DP · Interval DP · Fenwick Trees · String Hashing · Strings in Depth · Git & Diff.