This chapter covers the first two steps: recursion and memoization. Tabulation comes next.
What Is a Subsequence?
Before anything else, this needs to be clear.
A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters. The selected characters don't have to be adjacent.
String: A B C D E
Valid subsequences:
ACE (positions 1, 3, 5)
ABD (positions 1, 2, 4)
BDE (positions 2, 4, 5)
ABCDE (the whole string)
A (just the first character)
"" (empty — valid)
Not a valid subsequence:
CA (order is reversed)
The key point: gaps are allowed, but order is not.
What Is the Longest Common Subsequence?
Given two strings, find the longest subsequence that appears in both.
X = ABCDGH
Y = ABEDFW
Some common subsequences: A, AB, ABD, ABDH
The longest one is ABDH with length 4. That's the LCS.
The characters must appear in the same relative order in both strings, but they don't need to be adjacent in either.
Why This Is a DP Problem
Look at the last characters of both strings.
X = A B C D G H → last character: H
Y = A B E D F W → last character: W
Two cases arise.
Case 1: Last characters match.
If X[m-1] == Y[n-1], that character is part of the LCS. Include it and reduce both strings by one.
LCS(X, Y, m, n) = 1 + LCS(X, Y, m-1, n-1)
Case 2: Last characters don't match.
If X[m-1] != Y[n-1], you don't know which one to drop. So you try both and take the better result.
LCS(X, Y, m, n) = max(
LCS(X, Y, m-1, n), # drop last char of X
LCS(X, Y, m, n-1) # drop last char of Y
)
These two cases completely define the recursive structure.
Base Case
The smallest valid input is when either string runs out of characters.
X = "" or Y = ""
An empty string has no characters to share. The LCS is zero.
if m == 0 or n == 0:
return 0
Always design the base case first. Ask: what is the smallest input where the answer is obvious?
The Recursive Solution
Base case plus choice diagram gives you the full recursion directly.
class Solution:
def lcs(self, X, Y, m, n):
# Base case: one string is empty, no common subsequence
if m == 0 or n == 0:
return 0
# Last characters match — include and shrink both
if X[m - 1] == Y[n - 1]:
return 1 + self.lcs(X, Y, m - 1, n - 1)
# Last characters don't match — try dropping from either side
else:
return max(
self.lcs(X, Y, m - 1, n),
self.lcs(X, Y, m, n - 1)
)
def longestCommonSubsequence(self, X, Y):
m = len(X)
n = len(Y)
return self.lcs(X, Y, m, n)
The code is a direct translation of the choice diagram. Nothing is added beyond base case and two cases.
Why the Recursive Solution Gets Slow
When characters don't match, two recursive calls are made. Each of those makes two more. The tree grows exponentially.
Worse, the same state appears multiple times through different paths.
LCS(m, n)
├── LCS(m-1, n)
│ ├── LCS(m-2, n)
│ └── LCS(m-1, n-1) ← appears here
└── LCS(m, n-1)
├── LCS(m-1, n-1) ← and here again
└── LCS(m, n-2)
LCS(m-1, n-1) is calculated twice from the top level alone. Deeper in the tree, the overlap gets worse. For long strings, this becomes too slow.
The fix is the same as it was in the Knapsack series: store the answer the first time, reuse it every time after.
Memoization
The state is defined by two values: m and n. So the cache is a 2D table of size (m+1) × (n+1).
The +1 on each dimension is because m and n range from 0 to their respective lengths. Zero is a valid state (it's the base case), so it needs a slot in the table.
Why initialise with -1 and not 0
0 is a valid LCS answer. For example:
X = ABC
Y = XYZ
These strings share no characters. LCS = 0. If the table is initialised to zero, you can't tell whether a cell holds a computed answer of zero or an unvisited state. So we use -1 as the sentinel.
-1 → not computed yet
0 → computed, answer is 0
>0 → computed, answer is this value
This is the same reasoning as using None in Count of Subsets (Chapter 4), where False was a valid answer and couldn't serve as the placeholder.
Common mistake: initialising with 0 and then checking if T[m][n] != 0. This skips recomputing incorrectly when the real answer is zero.
# WRONG
if T[m][n] != 0:
return T[m][n]
# CORRECT
if T[m][n] != -1:
return T[m][n]
The Memoized Solution
class Solution:
def lcs(self, X, Y, m, n):
# Base case
if m == 0 or n == 0:
return 0
# Return stored answer if already computed
if self.T[m][n] != -1:
return self.T[m][n]
# Match: include character, shrink both strings
if X[m - 1] == Y[n - 1]:
self.T[m][n] = 1 + self.lcs(X, Y, m - 1, n - 1)
# No match: try both options, take the better one
else:
self.T[m][n] = max(
self.lcs(X, Y, m - 1, n),
self.lcs(X, Y, m, n - 1)
)
return self.T[m][n]
def longestCommonSubsequence(self, X, Y):
m = len(X)
n = len(Y)
# -1 means not yet computed
self.T = [[-1] * (n + 1) for _ in range(m + 1)]
return self.lcs(X, Y, m, n)
The recursive logic is unchanged. Two lines added: the cache check at the top, the store before returning. That's memoization.
The LCS Pattern to Remember
Base case:
m == 0 or n == 0 → return 0
Choice:
X[m-1] == Y[n-1] → 1 + LCS(m-1, n-1)
X[m-1] != Y[n-1] → max(LCS(m-1, n), LCS(m, n-1))
Memoization:
Table size: (m+1) × (n+1)
Initialise with -1
Check before computing, store after
What You Now Understand
LCS is not Knapsack. The inputs are two strings, not an array and a capacity. The table is indexed by string lengths, not items and weight. The choice is match-or-no-match, not take-or-skip.
But the process is the same. Base case first. Choices second. Recursion from those two. Repeated states observed. Memoization added with two lines.
The next chapter converts this recursion into a bottom-up tabulation. Once you see how m-1 and n-1 in the recursion map to i-1 and j-1 in the table, the entire LCS family of problems becomes much easier to build.
Top comments (0)