DSA · Dynamic Programming · #101
Longest Common Subsequence
Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke
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 by deleting some (possibly zero) characters 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 common to both. Implement `longestCommonSubsequence(text1, text2)` returning an integer length.
Examples
text1 = "abcde", text2 = "ace"→3— The longest common subsequence is "ace", with length 3.text1 = "abc", text2 = "abc"→3— The longest common subsequence is "abc".text1 = "abc", text2 = "def"→0— There is no common subsequence, so the result is 0.
Constraints
- · 1 <= text1.length, text2.length <= 1000
- · text1 and text2 consist of lowercase English characters only.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.