DSA problem
Longest Common Subsequence
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. For example, "ace" is a subsequence of "abcde" while "aec" is not. A common subsequence of two strings is a subsequence that is common to both strings.
This problem is the canonical introduction to two-dimensional string dynamic programming. Brute force enumerates all 2^m subsequences of text1 and checks each against text2, which is exponential. The DP refinement notices a clean recurrence: if text1[i-1] == text2[j-1] then the optimal LCS ending at indices i, j extends the LCS of the strict prefixes by one; otherwise it inherits the better of the two shorter prefix pairs.
The optimal approach builds a 2D table dp[i][j] of size (m+1) x (n+1) where dp[i][j] stores the LCS length for text1[0..i) and text2[0..j). The recurrence is dp[i][j] = dp[i-1][j-1] + 1 on match, else max(dp[i-1][j], dp[i][j-1]). This runs in O(m * n) time and O(m * n) space. Because the recurrence only references the previous row, the space can be compressed to a single 1D array of length min(m, n) + 1, giving the production-grade O(min(m, n)) space solution.
Examples
text1 = "abcde", text2 = "ace"3text1 = "abc", text2 = "abc"3text1 = "abc", text2 = "def"0Constraints
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.