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".
A **common subsequence** of two strings is a subsequence that is common to both strings.
Examples
text1 = "abcde", text2 = "ace"3text1 = "abc", text2 = "abc"3text1 = "abc", text2 = "def"0text1 = "abc", text2 = "ac"2Constraints
1 <= text1.length, text2.length <= 1000text1 and text2 consist of only lowercase English characters.
💡 Hints
Hint 1
Use a 2D dynamic programming grid where dp[i][j] stores the length of the LCS for text1[0..i-1] and text2[0..j-1].
Hint 2
If text1[i-1] matches text2[j-1], take the diagonal value plus one: dp[i][j] = dp[i-1][j-1] + 1.
Hint 3
If characters do not match, take the maximum of the top cell and left cell: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Algorithm Complexity
Official asymptotic Big-O runtime and auxiliary memory analysis
2D tabular dynamic programming. Build an (M+1) x (N+1) grid. If characters match, take dp[i-1][j-1] + 1. Otherwise, take max(dp[i-1][j], dp[i][j-1]).
Fills a 2D dynamic programming grid of size (M + 1) × (N + 1) where each cell transition computes in O(1).
The 2D table requires (M + 1) × (N + 1) integer storage cells.
🌍 Real-World Use Cases
Computing line-by-line diffs between committed file versions using the Myers diff algorithm based on Longest Common Subsequence.
★ Premium Challenge
Longest Common Subsequence is classified as a premium problem.