Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.
For example, given text1 = "abcde" and text2 = "ace", the longest common subsequence is "ace" with length 3.
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Think about comparing characters one at a time from each string and building a 2D table.
- Hint 2
If characters match, the LCS length increases by 1 from the diagonal. If not, take the max of skipping one character from either string.
- Hint 3
dp[i][j] = length of LCS of text1[0..i-1] and text2[0..j-1]. If text1[i-1] == text2[j-1], dp[i][j] = dp[i-1][j-1] + 1. Otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.