Skip to content

142 — Longest Common Subsequence

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

142 — Longest Common Subsequence

LeetCode 1143 · Medium. Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence 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. If there is no common subsequence, return 0.

🍽️ Intuition

Picture two editors comparing drafts of the same document, sentence by sentence, looking for the longest run of sentences that appears in both — in order, but not necessarily back-to-back. Standing at sentence i of draft one and sentence j of draft two, there are only two possibilities: either the current sentences match, in which case they're worth "locking in" and you move on to the sub-problem one sentence earlier in both drafts, or they don't match, in which case the best you can do is whichever is better — dropping the current sentence of draft one, or dropping the current sentence of draft two. That's a question answerable purely from three neighboring smaller answers, which is exactly what a 2-D DP grid is built for.

🚩 Pattern-Recognition Cue

"Longest common subsequence between two strings" is the archetypal two-sequence 2-D DP tell: describing "how far along am I" takes two indices — one into each string — so the natural state space is a grid, and each cell depends only on its up, left, and diagonal neighbors.

🐢 Brute Force

Recurse on the two suffixes starting at indices i and j, branching into "skip a character of text1" or "skip a character of text2" whenever the current characters don't match, with no memoization.

func longestCommonSubsequenceBruteForce(_ text1: String, _ text2: String) -> Int {
    let s1 = Array(text1)
    let s2 = Array(text2)

    func lcs(_ i: Int, _ j: Int) -> Int {
        if i == s1.count || j == s2.count { return 0 }
        if s1[i] == s2[j] {
            return 1 + lcs(i + 1, j + 1)
        }
        return max(lcs(i + 1, j), lcs(i, j + 1))
    }

    return lcs(0, 0)
}

// smoke test
print(longestCommonSubsequenceBruteForce("abcde", "ace"))     // 3
print(longestCommonSubsequenceBruteForce("abc", "abc"))        // 3
print(longestCommonSubsequenceBruteForce("abc", "def"))        // 0

Big-O: O(2^(m+n)) time in the worst case — every mismatch branches two ways, and the same (i, j) pairs are re-explored down many different branches. O(m + n) space for the recursion stack.

🚀 Optimal

Fill an (m+1) x (n+1) table where dp[i][j] is the LCS length between the first i characters of text1 and the first j characters of text2 — a character match extends the diagonal cell by one; a mismatch takes the better of dropping one character from either string.

func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
    let s1 = Array(text1)
    let s2 = Array(text2)
    let m = s1.count
    let n = s2.count
    guard m > 0 && n > 0 else { return 0 }

    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)

    for i in 1...m {
        for j in 1...n {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[m][n]
}

// smoke test — same cases as the brute force
print(longestCommonSubsequence("abcde", "ace"))     // 3
print(longestCommonSubsequence("abc", "abc"))        // 3
print(longestCommonSubsequence("abc", "def"))        // 0

Big-O: O(m · n) time — every cell is filled exactly once from at most three already-known neighbors. O(m · n) space for the dp table.

🔑 The Key Insight

Both versions make the exact same decision at every (i, j) pair — match and recurse diagonally, or drop a character from one string and take the better result — but the brute force treats every (i, j) as a brand-new problem no matter how many different branches arrive at it, so the same suffix pairs are re-solved exponentially many times. The optimal version fills the table row by row, so dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] are always already-finished answers by the time dp[i][j] needs them. Reusing three already-solved neighbors instead of re-branching from scratch is what turns exponential suffix comparisons into a flat O(m · n) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — this problem is chapter 27's worked example: two sequences, one on each axis, a table filled from the up/left/diagonal neighbors.
  • Arrays and Strings — both strings are converted to [Character] arrays for O(1) indexed access, and the dp table is a plain 2-D array.

🧸 Memory Sentence

Longest Common Subsequence is the two-editors grid: a character match locks in the diagonal cell plus one, and a mismatch inherits the better of "drop from the top string" or "drop from the left string."

✅ Check Your Understanding

  1. Why does a character match look at dp[i-1][j-1] (the diagonal), while a mismatch looks at dp[i-1][j] and dp[i][j-1] (up and left) instead of also considering the diagonal?
  2. Trace longestCommonSubsequence("abc", "abc") far enough to explain why every cell on the main diagonal of the table increases by exactly one.
  3. What would change in the recurrence if the problem asked for the longest common substring (contiguous) instead of subsequence? Which cell(s) would you need to track the maximum across instead of just reading dp[m][n]?

⬅️ Previous: Unique Paths · Next: Best Time to Buy and Sell Stock with Cooldown ➡️

Clone this wiki locally