Longest Common Subsequence
Given two strings, return the length of their longest common subsequence (LCS). A subsequence maintains relative order but needn't be contiguous.
Example
abcde ace
3
- The inputs are two lowercase strings,
text1=abcde(length ) andtext2=ace(length ). A common subsequence is a string you can get from both by deleting characters without reordering the ones that remain. - Delete
banddfromabcdeand you getace, which is already all oftext2. Soaceis a common subsequence of length . - No common subsequence can be longer than the shorter string, and
text2only has characters. So is the maximum and the output is3. - Order matters, not just shared letters. If the second string were "aec", both strings would still contain
a,cande, but inabcdetheccomes before thee. The best you could keep is "ac" or "ae", so the answer would drop to . - Notice that the output is a single integer, the length. You never need to return the subsequence itself, and when two strings share no letters at all the answer is .
Constraints
- 1 <= len(text1), len(text2) <= 1000
- Strings consist of lowercase English letters