601. Longest Common Subsequence
A subsequence of a string is whatever remains after deleting zero or more characters, keeping the surviving characters in their original order — so "ace" is a subsequence of "abcde", while "aec" is not. A common subsequence of two strings is a string that is a subsequence of both.
Your function receives two lowercase strings text1 and text2 and returns the length of their longest common subsequence, or 0 if they share none.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: Delete b and d from abcde and you are left with ace, which is all of text2 — a common subsequence of length 3, and no longer one exists.
Example 2:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: The strings have no character in common, so the only common subsequence is the empty string.
Constraints:
- 1 ≤ text1.length, text2.length ≤ 1000
- text1 and text2 consist of lowercase English letters only.
Hints:
Compare the last characters (or the first). If they are equal, they can safely be the final matched pair — the answer is 1 plus the LCS of the two prefixes. If they differ, at least one of them contributes nothing.
That gives a recurrence on (i, j) = (prefix of text1, prefix of text2). There are only (n+1)·(m+1) distinct states — memoize or fill a table instead of recursing blindly.
In the bottom-up table, `dp[i][j]` = LCS of the first i chars of text1 and first j chars of text2: `dp[i][j] = dp[i-1][j-1] + 1` on a match, else `max(dp[i-1][j], dp[i][j-1])`. Row i only reads row i−1, so two rows suffice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: text1 = "abcde", text2 = "ace"
Expected output: 3