Longest Common Subsequence
Problem Statement
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings.
Constraints:
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters.
Input Format:
- Two strings, text1 and text2
Output Format:
- Return an integer representing the length of the longest common subsequence.
Examples:
Example 1:
Input:
text1 = "abcde", text2 = "ace"
Output:
3
Explanation:
The longest common subsequence is "ace" and its length is 3.
Example 2:
Input:
text1 = "abc", text2 = "abc"
Output:
3
Explanation:
The longest common subsequence is "abc" and its length is 3.
Example 3:
Input:
text1 = "abc", text2 = "def"
Output:
0
Explanation:
There is no common subsequence, so return 0.
Solutions
Dynamic Programming Approach
Use a 2D DP table where dp[i][j] represents the length of the LCS of text1[0...i-1] and text2[0...j-1]. If characters match, we add 1 to the LCS of the strings without these characters. Otherwise, we take the maximum of excluding one character from either string.
Space-Optimized Dynamic Programming
Optimize the space complexity by using only two rows in the DP table, since each cell only depends on the current and previous row.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize a 2D DP table of size (m+1) x (n+1) filled with zeros, where m=5 and n=3
- i=1, j=1: text1[0]='a' matches text2[0]='a', dp[1][1] = dp[0][0] + 1 = 1
- i=1, j=2: text1[0]='a' doesn't match text2[1]='c', dp[1][2] = max(dp[0][2], dp[1][1]) = 1
- i=1, j=3: text1[0]='a' doesn't match text2[2]='e', dp[1][3] = max(dp[0][3], dp[1][2]) = 1
- i=2, j=1: text1[1]='b' doesn't match text2[0]='a', dp[2][1] = max(dp[1][1], dp[2][0]) = 1
- i=2, j=2: text1[1]='b' doesn't match text2[1]='c', dp[2][2] = max(dp[1][2], dp[2][1]) = 1
- i=2, j=3: text1[1]='b' doesn't match text2[2]='e', dp[2][3] = max(dp[1][3], dp[2][2]) = 1
- i=3, j=1: text1[2]='c' doesn't match text2[0]='a', dp[3][1] = max(dp[2][1], dp[3][0]) = 1
- i=3, j=2: text1[2]='c' matches text2[1]='c', dp[3][2] = dp[2][1] + 1 = 2
- i=3, j=3: text1[2]='c' doesn't match text2[2]='e', dp[3][3] = max(dp[2][3], dp[3][2]) = 2
- i=4, j=1: text1[3]='d' doesn't match text2[0]='a', dp[4][1] = max(dp[3][1], dp[4][0]) = 1
- i=4, j=2: text1[3]='d' doesn't match text2[1]='c', dp[4][2] = max(dp[3][2], dp[4][1]) = 2
- i=4, j=3: text1[3]='d' doesn't match text2[2]='e', dp[4][3] = max(dp[3][3], dp[4][2]) = 2
- i=5, j=1: text1[4]='e' doesn't match text2[0]='a', dp[5][1] = max(dp[4][1], dp[5][0]) = 1
- i=5, j=2: text1[4]='e' doesn't match text2[1]='c', dp[5][2] = max(dp[4][2], dp[5][1]) = 2
- i=5, j=3: text1[4]='e' matches text2[2]='e', dp[5][3] = dp[4][2] + 1 = 3
- The length of the LCS is dp[5][3] = 3
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the dynamic programming table and how it's filled step by step to find the longest common subsequence.
Key visualization elements:
- matching characters
- current cell
- dp table state
Implementation Notes
This is a classic dynamic programming problem that introduces the concept of finding a common pattern between two sequences. Understanding this problem helps with various string comparison and sequence alignment problems.