Skip to content
Tutorials Center
My learning

Topics

Lesson 154 of 225 ยท Dynamic Programming

LCS and Edit Distance

Master two classic string DPs in Python: longest common subsequence and substring, plus Levenshtein edit distance, with tables and reconstruction.

How similar are two strings? Diff tools, spell checkers, DNA comparison and plagiarism detectors all need a number for "how close are these two texts". Two dynamic programming problems answer that question in different ways:

  • Longest common subsequence (LCS): the longest sequence of characters that appears in both strings in the same order, but not necessarily next to each other.
  • Edit distance (Levenshtein distance): the minimum number of single-character edits (insert, delete, replace) that turn one string into the other.

Both use a two-dimensional table whose cell (i, j) answers the question for the first i characters of one string and the first j characters of the other. If you have seen the LIS and knapsack tables, this is the same idea with two string indexes instead of an item index and a capacity.

Longest common subsequence

For "ABCBDAB" and "BDCABA", one common subsequence is "BCBA" (length 4). Characters are picked in order from each string, skipping freely.

Brute force. Generate all 2^m subsequences of the first string and check each against the second. That is exponential.

State. dp[i][j] = the LCS length of the first i characters of a and the first j characters of b.

Transition. Compare the last characters a[i-1] and b[j-1]:

TEXT
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])
dp[0][*] = dp[*][0] = 0

If the last characters match, they can both be part of the answer, so extend the diagonal. If not, at least one of them is unused: drop the last character of a or of b and keep the better result.

Here is the table for a = "ABCB" and b = "BDCAB":

TEXT
        ""  B  D  C  A  B
   ""    0  0  0  0  0  0
   A     0  0  0  0  1  1
   B     0  1  1  1  1  2
   C     0  1  1  2  2  2
   B     0  1  1  2  2  3

The bottom-right cell is the answer: 3 (for example "BCB"). Filling the table costs O(m x n) time and space for strings of lengths m and n.

Python LCS length with a DP table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reconstructing the subsequence

Walk back from the bottom-right corner. If the characters match, take that character and go diagonally; otherwise move toward the neighbor with the larger value.

Python Recover an actual LCS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Several different longest subsequences may exist; this code returns one of them.

Saving space

Row i only needs row i - 1. If you only want the length, keep two rows and the space drops to O(n). (Rebuilding the string needs the full table, or a divide-and-conquer trick called Hirschberg's algorithm.)

Longest common substring

A substring must be contiguous. The recurrence is simpler, but the meaning of a cell changes: dp[i][j] is the length of the common substring that ends at a[i-1] and b[j-1].

TEXT
if a[i-1] == b[j-1]:   dp[i][j] = dp[i-1][j-1] + 1
else:                  dp[i][j] = 0        <- the run is broken
answer = the largest value anywhere in the table

Note the two differences from LCS: a mismatch resets to 0, and the answer is the maximum cell, not the corner.

Python Longest common substring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This version keeps just two rows, so the space is O(n). For very long strings, suffix structures do it in near-linear time.

Edit distance (Levenshtein)

Turn "kitten" into "sitting" with the fewest edits. Allowed operations, each costing 1:

  1. Insert a character.
  2. Delete a character.
  3. Replace a character with another.

kitten -> sitten (replace k with s) -> sittin (replace e with i) -> sitting (insert g): 3 edits.

State. dp[i][j] = the minimum edits to turn the first i characters of a into the first j characters of b.

Base cases. dp[i][0] = i (delete all i characters) and dp[0][j] = j (insert all j characters).

Transition. Look at the last characters:

TEXT
if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1]                   (no edit needed)
else:
    dp[i][j] = 1 + min(dp[i-1][j-1],          (replace)
                       dp[i-1][j],            (delete from a)
                       dp[i][j-1])            (insert into a)

The table for "cat" to "cut":

TEXT
        ""  c  u  t
   ""    0  1  2  3
   c     1  0  1  2
   a     2  1  1  2
   t     3  2  2  1

The answer, dp[3][3] = 1, is one replace (a becomes u).

Python Edit distance with a printed table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Showing the edits

Walk back through the table, choosing the move that explains each cell. This turns a number into a readable edit script.

Python Print the edit script

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Edit distance runs in O(m x n) time. Keeping two rows gives O(min(m, n)) space for the number, though the script needs the full table.

If only insertions and deletions are allowed (no replace), the minimum number of edits is m + n - 2 x LCS: keep the common subsequence and delete or insert everything else. The version with replacement can be cheaper, because a replace fixes two mismatched characters at once.

Python Space-optimised and indel distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Off-by-one indexes. The table is (m + 1) x (n + 1), and cell (i, j) compares a[i - 1] with b[j - 1].
  • Forgetting edit-distance base cases (dp[i][0] = i, dp[0][j] = j).
  • Building the table with [[0] * n] * m, which makes every row the same list. Use a comprehension, as above.
  • Mixing up subsequence and substring. Substring resets to 0 on a mismatch.
  • Returning the table corner for the substring problem. It needs the maximum over all cells.
  • Assuming the reconstructed answer is unique. Ties exist.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When a[i-1] == b[j-1], how is dp[i][j] computed in LCS?

    A matching last character extends the best answer for both strings without it, so we add 1 to the diagonal cell.
  2. 2. What is the LCS length of 'ABCBDAB' and 'BDCABA'?

    One longest common subsequence is BCBA, and no common subsequence of length 5 exists.
  3. 3. What is the edit distance between 'kitten' and 'sitting'?

    Replace k with s, replace e with i, and insert g: three edits.
  4. 4. How does the longest common SUBSTRING recurrence differ from LCS on a mismatch?

    A substring must be contiguous, so a mismatch ends the run. The answer is the largest cell anywhere, not the bottom-right corner.
  5. 5. What are the base cases dp[i][0] and dp[0][j] for edit distance?

    Turning a string of length i into the empty string needs i deletions, and building a string of length j from nothing needs j insertions.

Summary

  • LCS: dp[i][j] is the answer for the first i and j characters; matches extend the diagonal, mismatches take the larger neighbor. O(m x n) time.
  • Longest common substring resets to 0 on a mismatch and answers with the largest cell.
  • Edit distance has base cases i and j, and on a mismatch costs 1 + min(replace, delete, insert).
  • Walk back through the table to reconstruct the subsequence or the edit script.
  • Two rows are enough when you only need the number.
  • With insert/delete only, the distance is m + n - 2 x LCS.

Next: DP on Grids