Longest Common Subsequence

Welcome back, DP adventurer

In Fibonacci Series, you saw how caching or tabulating smaller answers prevents repeated work.

Now we level up: instead of a 1D sequence, Longest Common Subsequence uses a 2D DP table to compare two strings.

By the end, you will be able to answer questions like:

What is the longest sequence of characters that appears in both NARUTO and BORUTO, in the same relative order?

That sequence is RUTO, length 4.

This pattern appears in diff tools, DNA comparison, spell correction, plagiarism detection, and version control.

The key definition

A subsequence keeps characters in the same relative order, but it does not need to be contiguous.

For NARUTO:

• NTO is a subsequence: N _ _ _ T O
• RUTO is a subsequence: _ _ R U T O
• RUN is not a subsequence because N appears before R

A substring must be contiguous. So RUT is both a substring and a subsequence, but NTO is only a subsequence.

LCS asks for the longest sequence that two strings can both form by deleting characters only.

For the string ABCDE, which option is a valid subsequence but not a substring?

Prefixes make the problem smaller

For strings a and b, define:

dp[i][j] = length of the LCS between a[:i] and b[:j]

That means:

• i counts how many characters we use from a
• j counts how many characters we use from b
• dp[0][j] = 0 because an empty string has no common subsequence
• dp[i][0] = 0 for the same reason

The recurrence has two cases:

If the current characters match

If a[i - 1] == b[j - 1], that character can extend the best LCS from the smaller prefixes:

dp[i][j] = 1 + dp[i - 1][j - 1]

If they do not match

We cannot use both current characters together, so we try skipping one side:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

This is the same DP mindset from Fibonacci, but each answer depends on neighboring cells in a grid instead of earlier numbers in a line.

Fill in the recurrence.

If a[i - 1] == b[j - 1], then:

dp[i][j] = ____

Memoized recursion

Since you already used memoization in Fibonacci Series, this should feel familiar.

Let solve(i, j) mean:

LCS length of a[i:] and b[j:]

At each step:

• If either index reaches the end, return 0
• If characters match, take 1 + solve(i + 1, j + 1)
• Otherwise, skip one character from either string and take the better result

The cache prevents the same (i, j) pair from being recomputed.

```python
from functools import lru_cache


def lcs_length_top_down(a, b):
    @lru_cache(None)
    def solve(i, j):
        if i == len(a) or j == len(b):
            return 0

        if a[i] == b[j]:
            return 1 + solve(i + 1, j + 1)

        return max(solve(i + 1, j), solve(i, j + 1))

    return solve(0, 0)


print(lcs_length_top_down("NARUTO", "BORUTO"))
print(lcs_length_top_down("ABCBDAB", "BDCABA"))
```

Tabulation version

Now we build the table directly.

This is usually the clearest LCS implementation in interviews because the table mirrors the recurrence exactly.

We create a (len(a) + 1) x (len(b) + 1) grid. The extra row and column represent empty prefixes, which naturally start at 0.

Then we fill row by row.

```python

def lcs_length_bottom_up(a, b):
    rows, cols = len(a) + 1, len(b) + 1
    dp = [[0] * cols for _ in range(rows)]

    for i in range(1, rows):
        for j in range(1, cols):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1], dp


length, table = lcs_length_bottom_up("ABC", "AC")
print("LCS length:", length)
print("DP table:")
for row in table:
    print(row)
```

True or false?

In the bottom-up LCS table, dp[i][j] only depends on cells that are already known if we fill the table from top-left toward bottom-right.

Length is useful, but the string is better

The table gives the LCS length at dp[len(a)][len(b)].

To reconstruct one actual LCS, walk backward:

• If a[i - 1] == b[j - 1], that character belongs to the answer
• Move diagonally to (i - 1, j - 1)
• Otherwise, move toward the larger neighbor: up or left

There can be multiple valid LCS strings. Returning any one of them is usually acceptable unless the problem states otherwise.

```python

def lcs_string(a, b):
    rows, cols = len(a) + 1, len(b) + 1
    dp = [[0] * cols for _ in range(rows)]

    for i in range(1, rows):
        for j in range(1, cols):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    i, j = len(a), len(b)
    answer = []

    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            answer.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(reversed(answer))


print(lcs_string("NARUTO", "BORUTO"))
print(lcs_string("ABCBDAB", "BDCABA"))
```

Complexity

Let:

• n = len(a)
• m = len(b)

The standard LCS table has:

• Time: O(n * m) because every cell is computed once
• Space: O(n * m) for the full table

If you only need the length, you can compress space to keep just the previous row and current row. But if you want to reconstruct the actual subsequence, the full table is the most straightforward approach.

Takeaway

LCS is the first major 2D DP pattern in this course:

1. Define a prefix-based state
2. Write match and mismatch transitions
3. Fill the table in dependency order
4. Optionally backtrack to recover the answer

Next, we will use similar DP discipline on optimization with capacity constraints in 0/1 Knapsack Problem.

For the standard bottom-up LCS table between strings of lengths n and m, what are the time and space complexities?