Watch 10 video solutions for Longest Common Subsequence, a medium level problem involving String, Dynamic Programming. This walkthrough by take U forward has 598,553 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
"ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings.
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 such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000text1 and text2 consist of only lowercase English characters.Problem Overview: Given two strings text1 and text2, find the length of their longest common subsequence (LCS). A subsequence keeps the relative order of characters but may skip characters. The task is to determine the maximum number of characters that appear in both strings in the same order.
Approach 1: Dynamic Programming (2D Table) (Time: O(m*n), Space: O(m*n))
The standard solution uses a 2D DP table where dp[i][j] represents the length of the LCS for the prefixes text1[0..i-1] and text2[0..j-1]. Iterate through both strings using nested loops. If the current characters match (text1[i-1] == text2[j-1]), extend the subsequence with dp[i][j] = 1 + dp[i-1][j-1]. If they differ, carry forward the best result from either skipping a character in text1 or text2: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This builds the answer bottom-up while exploring all prefix combinations. The approach is widely used in dynamic programming problems involving strings, especially sequence comparison tasks such as edit distance and diff algorithms.
Approach 2: Optimized Dynamic Programming with Space Reduction (Time: O(m*n), Space: O(min(m,n)))
The 2D DP table only depends on the previous row and the current row. You can reduce memory usage by storing just one row (or two rows) instead of the entire matrix. Iterate through the characters of the first string while updating a 1D array that represents the LCS values for the second string. Track the previous diagonal value (which corresponds to dp[i-1][j-1]) during iteration so you can compute matches correctly. This keeps the same transition logic but compresses the memory footprint significantly. The algorithm still processes every pair of characters, so the time complexity remains O(m*n), but the space drops to O(min(m,n)), which is useful when working with long strings or memory-constrained environments.
Recommended for interviews: Interviewers typically expect the classic 2D dynamic programming formulation first because it clearly demonstrates the recurrence relation and state transition. Once you show the correct DP state definition and transitions, discussing the space optimization shows deeper understanding and practical engineering judgment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (2D Table) | O(m*n) | O(m*n) | General case and easiest way to reason about the LCS recurrence during interviews |
| Space Optimized Dynamic Programming | O(m*n) | O(min(m,n)) | When strings are large and memory usage of the full DP matrix becomes expensive |