Longest Common Subsequence
Part of Practice: Grids & Two Strings
Given two strings text1 and text2, return the length of their longest common subsequence — the longest string that appears in both, keeping relative order but not requiring the characters to sit next to each other. If they share no characters, return 0.
A subsequence is what remains after deleting zero or more characters: "ace" is a subsequence of "abcde", but "aec" is not, because order must be preserved.
Constraints: 1 <= text1.length, text2.length <= 1000, lowercase English letters only.
Examples
- Input:
- text1 = "abcde", text2 = "ace"
- Output:
- 3
"ace" appears in both strings in order, and nothing longer does.
- Input:
- text1 = "abc", text2 = "abc"
- Output:
- 3
The whole string is common.
- Input:
- text1 = "abc", text2 = "def"
- Output:
- 0
No character is shared, so the only common subsequence is the empty string.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.