150NeetCode 150

112.Longest Common Subsequence

MediumBlind 752-D Dynamic Programming · 2/11
LeetCode #1143Video

Problem

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). If there is none, return 0.

A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining ones ("ace" is a subsequence of "abcde", "aec" is not). A common subsequence appears in both strings.

Examples

Input:  text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The LCS is "ace".
Input:  text1 = "abc", text2 = "abc"
Output: 3
Explanation: The whole string is common.
Input:  text1 = "abc", text2 = "def"
Output: 0
Explanation: No characters in common.

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • Both strings consist of lowercase English letters only.

💡 Key Insight

Compare the first characters of the two remaining suffixes. If they match, that character can always be part of an LCS, so take it and advance both: 1 + lcs(i + 1, j + 1). If they differ, at least one of them is not used — try skipping either: max(lcs(i + 1, j), lcs(i, j + 1)). The state is just the pair (i, j), giving an (m+1) x (n+1) table that can be compressed to one row.

Recursion (Brute Force)

TimeO(2^(m+n))SpaceO(m + n)

Intuition

Let lcs(i, j) be the LCS length of text1[i..] and text2[j..]. If either suffix is empty, the answer is 0. Otherwise apply the match / skip rule from the key insight.

Algorithm

  1. lcs(i, j):
    • If i == m or j == n, return 0.
    • If text1[i] == text2[j], return 1 + lcs(i + 1, j + 1).
    • Else return max(lcs(i + 1, j), lcs(i, j + 1)).
  2. Return lcs(0, 0).

Visualization

flowchart TD
    A["lcs(0,0)<br/>'abc' vs 'ac'<br/>a == a"] -->|"match +1"| B["lcs(1,1)<br/>'bc' vs 'c'<br/>b != c"]
    B -->|"skip b"| C["lcs(2,1)<br/>'c' vs 'c'<br/>match"]
    B -->|"skip c"| D["lcs(1,2)<br/>'bc' vs ''<br/>0"]
    C -->|"match +1"| E["lcs(3,2) = 0"]
    C --> F["lcs(2,1) = 1"]
    F --> G["lcs(1,1) = max(1, 0) = 1"]
    G --> H["lcs(0,0) = 1 + 1 = 2"]

Code

java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, 0, 0);
    }

    private int lcs(String a, String b, int i, int j) {
        if (i == a.length() || j == b.length()) {
            return 0; // one suffix is empty
        }
        if (a.charAt(i) == b.charAt(j)) {
            return 1 + lcs(a, b, i + 1, j + 1); // use the matching char
        }
        // drop a char from either string and keep the better result
        return Math.max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1));
    }
}

Complexity

  • Time: O(2^(m+n)) — the mismatch case branches twice and depth is up to m + n.
  • Space: O(m + n) — recursion depth.

Complexity Comparison

Approach Time Space
Recursion (Brute Force) O(2^(m+n)) O(m + n)
Top-Down Memoization O(m · n) O(m · n)
Bottom-Up 2-D Tabulation O(m · n) O(m · n)
Space-Optimized 1-D DP O(m · n) O(min(m, n))

Common Pitfalls

  • Confusing subsequence with substring — on a mismatch LCS takes max(up, left); it does not reset to 0 (that is longest common substring).
  • Off-by-one between dp indices and string indices: dp[i][j] compares text1[i-1] and text2[j-1].
  • In the 1-D version, forgetting to save the old dp[j] before overwriting it — then the diagonal value is lost.
  • Resetting prevDiag to 0 at the start of every row is required (dp[i-1][0] is always 0).
  • On a match, there is no need to also consider skipping — taking the match is never worse.