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.The Longest Common Subsequence (LCS) problem asks you to find the longest sequence that appears in the same relative order in two strings, though not necessarily contiguously. A brute-force approach would try all subsequences, but that quickly becomes impractical due to exponential growth.
The optimal strategy uses Dynamic Programming. Create a 2D DP table where dp[i][j] represents the length of the longest common subsequence between the first i characters of the first string and the first j characters of the second string.
If the current characters match, extend the subsequence from the previous state. If they do not match, take the maximum result from skipping a character in either string. This builds the solution incrementally from smaller subproblems. The standard DP approach runs in O(n × m) time. With further optimization, the space can be reduced using rolling arrays while keeping the same time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP Table) | O(n × m) | O(n × m) |
| Space Optimized DP (Rolling Array) | O(n × m) | O(min(n, m)) |
Abdul Bari
Use these hints if you're stuck. Try solving on your own first.
Try dynamic programming. DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j].
DP[i][j] = DP[i - 1][j - 1] + 1 , if text1[i] == text2[j] DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) , otherwise
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].
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.
1#include <stdio.h>
2#include <string.h>
3
4int longestCommonSubsequence(char* text1, char* text2)
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.
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.
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))
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the Longest Common Subsequence problem is a classic dynamic programming question frequently asked in technical interviews at FAANG and other top tech companies. It tests understanding of DP state transitions and optimization techniques.
The optimal approach uses dynamic programming. A 2D table stores the length of the longest subsequence for prefixes of both strings, allowing the problem to be solved in O(n × m) time by building results from smaller subproblems.
A dynamic programming table (usually a 2D array) is the most common data structure for solving LCS. It stores intermediate results for each pair of string prefixes, which prevents recomputation and improves efficiency.
Yes. Instead of storing the full 2D DP table, you can use two rows (or a single rolling array) because each state only depends on the previous row. This reduces space complexity to O(min(n, m)).
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.