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.
This approach uses dynamic programming to solve the problem by creating a 2D table to store the lengths of the longest common subsequences for different substrings. Each cell dp[i][j] in the table represents the longest common subsequence length of substrings text1[0..i-1] and text2[0..j-1]. The table is filled using the following rules:
text1[i-1] and text2[j-1] are equal, then dp[i][j] = dp[i-1][j-1] + 1.dp[i][j] = max(dp[i-1][j], dp[i][j-1]).The final answer is dp[text1.length][text2.length].
This C solution defines a function longestCommonSubsequence that calculates the longest common subsequence length using a 2D array dp. The program iteratively updates the table based on character matches and topological decision making (max operation). The main function demonstrates this by testing with two example strings and printing the result.
Time Complexity: O(n*m), where n and m are the lengths of text1 and text2 respectively.
Space Complexity: O(n*m) for the DP table.
This optimization reduces space complexity by only storing data for the current and the previous row. The idea remains the same - calculating the LCS length incrementally using a dynamic programming strategy. However, instead of a full 2D table, only two 1D arrays are used, effectively reducing space usage from O(n*m) to O(min(n, m)). This is achieved by noting that each row of the DP table depends only on the previous row. So, we use two arrays that swap every iteration.
The optimized C solution uses two arrays previous and current to store the LCS length for the current and last iteration. After computing each row, the current becomes the previous, thereby saving space. The solution is efficient both in terms of time and space compared to the full 2D table.
Time Complexity: O(n*m), where n is the length of text1 and m is the length of text2.
Space Complexity: O(min(n, m))
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n*m), where n and m are the lengths of |
| Optimized Dynamic Programming with Space Reduction | Time Complexity: O(n*m), where n is the length of |
| 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 |
Dp 25. Longest Common Subsequence | Top Down | Bottom-Up | Space Optimised | DP on Strings • take U forward • 598,553 views views
Watch 9 more video solutions →Practice Longest Common Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor