Longest Common Subsequence
MediumStringSorting
Description
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
Examples
Input:
text1 = "abcde", text2 = "ace"Output:
3Explanation:
The longest common subsequence is 'ace': a(pos 0), c(pos 2), e(pos 4) appear in order in both strings.
Input:
text1 = "abc", text2 = "def"Output:
0Explanation:
The strings share no common characters (a,b,c vs d,e,f), so there is no common subsequence.
Input:
text1 = "programming", text2 = "algorithm"Output:
3Explanation:
The longest common subsequence is "rgrm" (characters at positions r-g-r-m in both strings). Other valid LCS include "agrm" and "rgam", but they all have the same maximum length of 5.
Constraints
- •
1 ≤ text1.length, text2.length ≤ 1000 - •
text1 and text2 consist of lowercase English characters.
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.