Longest Common Subsequence
Problem
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. You may assume the input strings consist of only lowercase English letters.
- 1 ≤ text1.length, text2.length ≤ 1000
- text1 and text2 consist of only lowercase English characters.
Example
text1 = "abcde", text2 = "ace"3The longest common subsequence is "ace" with length 3. The algorithm explores the strings starting from index 0 in both. At index 0, characters match ('a' == 'a'), so it adds 1 and recurses on the next indices (1,1). At index 1 and 1, characters differ ('b' != 'c'), so it explores two paths: skipping 'b' in text1 or skipping 'c' in text2. It recursively computes the maximum length from these paths, eventually finding the longest subsequence length 3.
Approach
Straightforward Solution
A brute-force approach tries all subsequence combinations, resulting in exponential time complexity because it explores all subsets of characters in both strings.
Core Observation
The longest common subsequence problem exhibits optimal substructure: the solution for prefixes of the strings depends on solutions to smaller prefixes. Specifically, if characters match at current indices, the LCS length increases by one plus the LCS of the remaining substrings; otherwise, it is the maximum LCS length obtained by advancing one index in either string.
Path to Optimal
Recognizing the overlapping subproblems and optimal substructure leads to dynamic programming. The problem can be solved by defining a recursive function dp(i, j) that returns the LCS length of text1[i:] and text2[j:]. Memoization caches results to avoid redundant computations, reducing time complexity from exponential to polynomial.
Optimal Approach
Implement a top-down recursive function with memoization that returns 0 when either index reaches the end of its string. If characters at i and j match, return 1 plus dp(i+1, j+1). Otherwise, return the maximum of dp(i+1, j) and dp(i, j+1). Store results in a memo dictionary keyed by (i, j) to ensure each subproblem is solved once.
Time
O(m * n)
Each subproblem dp(i, j) corresponds to a unique pair of indices in text1 and text2. Since there are m * n such pairs and each is computed once due to memoization, the total time is O(m * n).
Space
O(m * n)
The memo dictionary stores results for each pair of indices, requiring O(m * n) auxiliary space. The recursion stack depth is at most m + n, which is O(m + n), but dominated by the memo size.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves making decisions at each position with overlapping subproblems and optimal substructure, model it as a recursive state with memoization to avoid redundant work and achieve polynomial time.
Solution
| 1 | class Solution:
|
| 2 | def longestCommonSubsequence(self, text1: str, text2: str) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, j):
|
| 6 | if i >= len(text1) or j >= len(text2):
|
| 7 | return 0
|
| 8 | if (i, j) in memo:
|
| 9 | return memo[(i, j)]
|
| 10 |
|
| 11 | if text1[i] == text2[j]:
|
| 12 | result = 1 + dp(i + 1, j + 1)
|
| 13 | else:
|
| 14 | result = max(dp(i + 1, j), dp(i, j + 1))
|
| 15 |
|
| 16 | memo[(i, j)] = result
|
| 17 | return result
|
| 18 |
|
| 19 | return dp(0, 0) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int longestCommonSubsequence(String text1, String text2) { |
| 6 | Map<String, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(0, 0, text1, text2, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(int i, int j, String text1, String text2, Map<String, Integer> memo) { |
| 12 | if (i >= text1.length() || j >= text2.length()) { |
| 13 | return 0; |
| 14 | } |
| 15 | String key = i + "," + j; |
| 16 | if (memo.containsKey(key)) { |
| 17 | return memo.get(key); |
| 18 | } |
| 19 | |
| 20 | int result; |
| 21 | if (text1.charAt(i) == text2.charAt(j)) { |
| 22 | result = 1 + dp(i + 1, j + 1, text1, text2, memo); |
| 23 | } else { |
| 24 | result = Math.max(dp(i + 1, j, text1, text2, memo), dp(i, j + 1, text1, text2, memo)); |
| 25 | } |
| 26 | |
| 27 | memo.put(key, result); |
| 28 | return result; |
| 29 | } |
| 30 | } |
| 1 | #include <string> |
| 2 | #include <unordered_map> |
| 3 | #include <utility> |
| 4 | #include <algorithm> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | int longestCommonSubsequence(string text1, string text2) { |
| 11 | unordered_map<string, int> memo; |
| 12 | return dp(0, 0, text1, text2, memo); |
| 13 | } |
| 14 | |
| 15 | private: |
| 16 | int dp(int i, int j, const string& text1, const string& text2, unordered_map<string, int>& memo) { |
| 17 | if (i >= (int)text1.size() || j >= (int)text2.size()) { |
| 18 | return 0; |
| 19 | } |
| 20 | string key = to_string(i) + "," + to_string(j); |
| 21 | auto it = memo.find(key); |
| 22 | if (it != memo.end()) { |
| 23 | return it->second; |
| 24 | } |
| 25 | |
| 26 | int result; |
| 27 | if (text1[i] == text2[j]) { |
| 28 | result = 1 + dp(i + 1, j + 1, text1, text2, memo); |
| 29 | } else { |
| 30 | result = max(dp(i + 1, j, text1, text2, memo), dp(i, j + 1, text1, text2, memo)); |
| 31 | } |
| 32 | |
| 33 | memo[key] = result; |
| 34 | return result; |
| 35 | } |
| 36 | }; |
| 1 | var longestCommonSubsequence = function(text1, text2) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(i, j) { |
| 5 | if (i >= text1.length || j >= text2.length) { |
| 6 | return 0; |
| 7 | } |
| 8 | const key = i + ',' + j; |
| 9 | if (memo.has(key)) { |
| 10 | return memo.get(key); |
| 11 | } |
| 12 | |
| 13 | let result; |
| 14 | if (text1[i] === text2[j]) { |
| 15 | result = 1 + dp(i + 1, j + 1); |
| 16 | } else { |
| 17 | result = Math.max(dp(i + 1, j), dp(i, j + 1)); |
| 18 | } |
| 19 | |
| 20 | memo.set(key, result); |
| 21 | return result; |
| 22 | } |
| 23 | |
| 24 | return dp(0, 0); |
| 25 | }; |
Step-by-Step Solution
Initialize Memoization Cache for Subproblem Results
| 3 | memo = {}
|
Objective
To create a dictionary that caches results of subproblems identified by index pairs (i, j) to avoid redundant recursive calls.
Key Insight
Memoization transforms the naive exponential recursion into polynomial time by storing the results of each unique subproblem. This cache acts as a memory of all previously solved states, enabling instant retrieval and preventing repeated work.
Interview Quick-Check
Core Logic
The memo dictionary keys are tuples (i, j) representing the current indices in text1 and text2, ensuring each subproblem is uniquely identified.
Common Pitfalls & Bugs
Forgetting to check the memo before recursive calls leads to exponential time due to repeated computations.
Recursively Compute LCS Length with Memoization
| 5 | def dp(i, j):
|
| 6 | if i >= len(text1) or j >= len(text2):
|
| 7 | return 0
|
| 8 | if (i, j) in memo:
|
| 9 | return memo[(i, j)]
|
| 11 | if text1[i] == text2[j]:
|
| 12 | result = 1 + dp(i + 1, j + 1)
|
| 13 | else:
|
| 14 | result = max(dp(i + 1, j), dp(i, j + 1))
|
| 16 | memo[(i, j)] = result
|
| 17 | return result
|
Objective
To define a recursive function that computes the LCS length for substrings starting at indices i and j, using memoization to cache results.
Key Insight
The recursion explores two cases: if characters match, the LCS length increases by one plus the result of the next indices; if not, it explores skipping a character in either string and takes the maximum. Memoization ensures each state is computed once, turning an exponential search into a polynomial-time solution.
Interview Quick-Check
Core Logic
The recursive function returns 0 when either index reaches the end, ensuring proper base cases and termination.
Core Logic
When characters match, the function adds 1 and recurses on the next indices, capturing the extension of the subsequence.
Core Logic
When characters differ, the function explores both possibilities of skipping one character from either string and takes the maximum, ensuring all subsequence paths are considered.
State & Boundaries
Memoization lookup before recursion prevents redundant calculations and ensures O(m*n) complexity.
Common Pitfalls & Bugs
Incorrect base case conditions or missing memo checks can cause infinite recursion or exponential time.
Return Final LCS Length from Starting Indices
| 19 | return dp(0, 0) |
Objective
To initiate the recursive computation from the start of both strings and return the final longest common subsequence length.
Key Insight
Starting the recursion at indices (0, 0) triggers the exploration of all subproblems in a top-down manner. The memoization ensures that each subproblem is solved once, and the final returned value is the length of the longest common subsequence for the entire strings.
Interview Quick-Check
Core Logic
The initial call dp(0, 0) represents the full problem and triggers the entire memoized recursion.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
if (i, j) in memo:Check if the current subproblem result is already cached in memo.
This lookup prevents recomputation of the same subproblem, ensuring the algorithm runs in polynomial time rather than exponential.
if i >= len(text1) or j >= len(text2):Check if either index has reached the end of its string, returning 0 as the base case.
This base case terminates recursion when one string is exhausted, as no further common subsequence can be found beyond this point.
return memo[(i, j)]Return the cached result if found.
Returning the memoized value immediately prunes the recursion tree, avoiding redundant work and improving efficiency.
result = 1 + dp(i + 1, j + 1)Calculate result as 1 plus the LCS length of the remaining substrings.
Adding one accounts for the matched character, and the recursive call explores the rest of the strings, building the subsequence length incrementally.
result = max(dp(i + 1, j), dp(i, j + 1))Calculate result as the maximum LCS length by skipping one character in either string.
Taking the maximum ensures the algorithm considers all subsequence paths, selecting the longest possible common subsequence.
memo[(i, j)] = resultCache the computed result for the current subproblem (i, j).
Storing the result ensures that future calls with the same indices can return instantly, preventing exponential recomputation.
memo = {}Initialize a memoization dictionary to cache subproblem results keyed by index pairs.
This cache is essential to avoid redundant recursive calls by storing the results of each unique subproblem, transforming exponential recursion into polynomial time.
if text1[i] == text2[j]:Check if characters at indices i and j match.
Matching characters extend the common subsequence by one, enabling a direct recursive step to the next indices.
else:Handle the case where characters do not match.
When characters differ, the algorithm must explore both possibilities of skipping one character from either string to find the maximum subsequence length.
return dp(0, 0)Start the recursive computation from the beginning of both strings and return the final LCS length.
This call triggers the entire memoized recursion, ensuring the full problem is solved efficiently and the correct answer is returned.
return 0Return 0 when base case is met.
Returning zero here correctly represents that no further subsequence length can be added beyond the string boundary.
return resultReturn the computed LCS length for the current indices.
Returning the result propagates the computed value up the recursion stack, enabling the final answer to be assembled.
def dp(i, j):Define the recursive function dp that computes LCS length starting from indices i and j.
Encapsulating the recursive logic in a helper function allows clean management of the state defined by the current indices in both strings.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to polynomial in this problem?
Because memoization ensures each unique subproblem (defined by indices i and j) is computed only once, preventing repeated exploration of the same states and collapsing an exponential recursion tree into a polynomial number of computations.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Longest Common Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Common Subsequence drill