Longest Common Subsequence
01 · Problem
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.
02 · Examples
text1 = "abcde", text2 = "ace"
3
The longest common subsequence is "ace" with length 3. Characters 'a', 'c', 'e' appear in both strings in the same relative order.
text1 = "abc", text2 = "abc"
3
The entire string "abc" is a common subsequence since both strings are identical.
03 · Constraints
- 011 <= text1.length, text2.length <= 1000
- 02text1 and text2 consist of only lowercase English characters
04 · Optimal complexity
- Time
- O(m * n)
- Space
- O(m * n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.