DSA Longest Common Subsequence
The longest common subsequence is the longest sequence of characters that appears in both strings in the same order. A prefix table finds its length one prefix pair at a time.
The problem
The longest common subsequence is the longest sequence of characters that appears in both strings in the same order. A subsequence keeps the order of the original string. It may skip characters.
The input is two strings. The output is one number. That number is the length of the longest shared subsequence.
The cases used in this article
cases = [
("stone", "longest", 3),
("abcde", "ace", 3),
("bridge", "fridge", 5),
("abc", "def", 0),
]
for a, b, expected in cases:
print(a, "vs", b, "->", expected)Read the last row with care. The two strings share no character at all. Their answer is zero, not one.
Intuition: shared letters are not enough
The first idea counts the letters that appear in both strings. That count feels like progress. It ignores order completely.
Order is the whole problem. Two strings can hold exactly the same letters and still share only a short subsequence.
The same letters, a short shared order
a = "abc"
b = "cba"
shared = len(set(a) & set(b))
print("shared letters:", shared)
print("letters of a in order:", list(a))
print("letters of b in order:", list(b))
print("one shared subsequence: 'a', length 1")The shared count is three. The longest common subsequence has length one. Any single letter works, and no two letters appear in the same order in both strings.
Brute force: list every subsequence and test it
A subsequence of a string comes from choosing a subset of its positions. The chosen positions keep their order. A string of length n has 2 to the power n subsets.
The brute force lists every subsequence of the first string. It tests each one against the second string. It keeps the longest one that passes.
The brute force, counted
def is_subseq(sub, word):
pos = 0
for ch in word:
if pos < len(sub) and ch == sub[pos]:
pos += 1
return pos == len(sub)
def lcs_brute(a, b):
best = 0
tested = 0
for mask in range(2 ** len(a)):
sub = "".join(a[i] for i in range(len(a)) if mask >> i & 1)
tested += 1
if len(sub) > best and is_subseq(sub, b):
best = len(sub)
return best, tested
for a, b in [("abcde", "ace"), ("stone", "longest")]:
best, tested = lcs_brute(a, b)
print(a, "vs", b, "->", best, "subsequences tested:", tested)Five letters already force 32 tests. Each extra letter doubles the list. The count, not the clock, shows the problem.
The optimal solution: a prefix table
A prefix is a starting slice of a string. The state dp[i][j] holds the answer for the first i characters of one string and the first j characters of the other.
A match of the two last characters extends the diagonal answer by one. A mismatch copies the better of the top and left answers. The bottom right cell holds the answer for the whole pair.
The prefix table on every case
def lcs_len(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):
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])
return dp[m][n]
cases = [
("stone", "longest", 3),
("abcde", "ace", 3),
("bridge", "fridge", 5),
("abc", "def", 0),
]
for a, b, expected in cases:
result = lcs_len(a, b)
print(a, "vs", b, "->", result, "expected:", expected, "match:", result == expected)All four cases pass. The table never lists a subsequence. It builds each answer from three smaller answers that are already final.
Walkthrough: abcde against ace
The walkthrough uses the third case pair in short form. The first string is abcde. The second string is ace.
Each row of the table belongs to one prefix of abcde. Each column belongs to one prefix of ace. The table grows one row at a time.
The finished table, row by row
def lcs_table(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):
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])
return dp
dp = lcs_table("abcde", "ace")
for row in dp:
print(row)
print("bottom right cell:", dp[5][3])The bottom right cell holds 3. That cell covers both full strings. The matching letters a, c and e give that length.
Complexity
The table fills one cell for each pair of prefixes, so its time is O(m times n) for string lengths m and n. The brute force tests 2 to the power n subsequences, so its time grows exponentially.
The table stores every cell, so its space is O(m times n). Only the length needs the full table in memory here, and two rows would hold enough for the length alone.
Counting the work at three sizes
for n in [5, 10, 20]:
print("length", n, "- brute subsequences:", 2 ** n, " table cells:", n * n)At length 20 the brute force passes one million tests. The table fills 400 cells. The gap comes from counting, not from timing.
Edge cases and pitfalls
An empty string shares no characters with anything. Its answer is zero. The table handles it with its zero border row and column.
The classic mistake compares a character with the wrong prefix end. Cell dp[i][j] reads a[i - 1] and b[j - 1]. The minus one exists because the table has an extra border row and column.
Edge cases, run
def lcs_len(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):
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])
return dp[m][n]
print("empty first:", lcs_len("", "abc"))
print("empty second:", lcs_len("abc", ""))
print("identical:", lcs_len("abc", "abc"))
print("no shared letter:", lcs_len("abc", "def"))
print("one shared letter:", lcs_len("abc", "cba"))Identical strings answer their full length. That row is a quick check on any new implementation. A table that fails it has an index error somewhere.
Exercise
Two strings end with the same character. What does the last table cell do?