Longest common subsequence

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• 0/1 knapsack recurrence? from Lesson 5.1.2
• Naive fib(5) calls? from Lesson 5.1.1
• Merge two sorted lists of sizes p, q: max comparisons? from Lesson 3.2.1

1 · The Hook

🎣

diff compares two files by finding the longest set of lines they share in order. DNA alignment does the same with letters. That is the longest common subsequence (LCS), and GATE has asked for both its length and the number of distinct LCSs.

2 · Predict First

🤔

A subsequence keeps characters in order but may skip some. What is a longest common subsequence of X = ABCBDAB and Y = BDCABA?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

For example BCBA (length 4): B, C, B, A appear in this order in both. No common subsequence of length 5 exists.

Recurrence

L[i][j] = length of an LCS of X[1..i] and Y[1..j].

• L[0][j] = L[i][0] = 0.
• If X[i] = Y[j]: L[i][j] = L[i − 1][j − 1] + 1.
• Else: L[i][j] = max(L[i − 1][j], L[i][j − 1]).

Answer L[m][n]. Θ(mn) time and space (Θ(min(m, n)) space for the length only).

Reconstruction

From (m, n): if the characters match, take it and go diagonally; else move to the larger of the up/left neighbours (if equal, both directions may lead to different LCSs).

Counting distinct LCSs

Follow all tie-branches and collect distinct strings. X = ABCBDAB, Y = BDCABA has 3 distinct LCSs of length 4: BCAB, BCBA, BDAB.

Not the same as substring

A common substring must be contiguous (a different DP: L[i][j] = L[i − 1][j − 1] + 1 on a match, else 0).

4 · Visual

LCS table for X = ABCBDAB (rows) and Y = BDCABA (columns):

5 · Worked Examples

Example 1 Easy

LCS length of AGGTAB and GXTXAYB?

Solution

4 (GTAB).

Example 2 Medium

How many table entries does the LCS DP fill for strings of lengths 30 and 40 (excluding row 0 and column 0)?

Solution

30 × 40 = 1,200, each in O(1): Θ(mn).

Example 3 GATE

Let x be the LCS length of qpqrr and pqprqrp, and y the number of distinct LCSs of that length. x + 10y = ?

Solution

x = 4 (qpqr, qprr, pqrr: y = 3). x + 10y = 34.

6 · GATE Traps

⚠️

• Subsequence ≠ substring: subsequences may skip characters.
• On a mismatch take the max of up and left; on a match, diagonal + 1.
• Count distinct LCS strings, not paths (different paths can give the same string).
• LCS is Θ(mn); the brute force over subsequences is exponential.

7 · Memory Hook

🧠

"Match: diagonal plus one. Mismatch: best of up and left."

8 · Connect the Dots

Chapter 5.1 is complete: the DP idea, knapsack and LCS. Chapter 5.2 adds interval DP (matrix chains) and more sequence DPs: subset sums, coin change, rod cutting, LIS and edit distance.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksLCS length

LCS length of ABCBDAB and BDCABA?

Numerical answer: ________

Q2NAT2 marksDistinct LCSs

How many distinct LCSs of maximum length do ABCDEF and ACBDFE have?

Numerical answer: ________

Q3NAT2 marksGATE pattern

x = LCS length of qpqrr and pqprqrp; y = number of distinct LCSs. x + 10y?

Numerical answer: ________

Q4MCQ1 markRecurrence

When X[i] ≠ Y[j], the LCS recurrence sets L[i][j] to:

• (A) L[i − 1][j − 1] + 1
• (B) L[i − 1][j − 1]
• (C) 0
• (D) max(L[i − 1][j], L[i][j − 1])

Q5NAT1 markTable entry

In the visual table, what is L[4][5] (prefix ABCB versus BDCAB)?

Numerical answer: ________

10 · Rule Card

• L[i][j] = L[i−1][j−1] + 1 on match; else max(L[i−1][j], L[i][j−1]); zeros on the borders.
• Θ(mn); reconstruct from (m, n); ties give multiple LCSs.
• Common substring: diagonal + 1 on match, else 0.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

subsequence vs substringlongest common subsequenceLCS tableLCS reconstructionnumber of distinct LCSslongest common substring

12 · Answer Vault