LeetCode · #1143

Longest Common Subsequence Solution

Given two strings, return the length of their longest common subsequence. Return 0 if none exists.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1143

🏗️

Pattern

DP — 2D string matching (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence can skip characters but must maintain relative order.

Example

 Input: text1 = "abcde", text2 = "ace" Output: 3 // LCS is "ace" 

Constraints

• 1 ≤ text1.length, text2.length ≤ 1000

Section Two · Approach 1

Recursion — O(2^(m+n))

Compare last characters: if they match, LCS includes it; if not, try dropping from either string and take the max. Exponential branching.

Why it works

The recursion correctly considers all possible subsequence alignments by either including matching characters or skipping from one string.

Why we can do better

Problem: Overlapping subproblems — lcs(i,j) is recomputed from multiple paths. A 2D table of size m×n stores each cell once, giving O(m·n).

Java — Recursive

 class Solution {
public int longestCommonSubsequence(String t1, String t2) {
return lcs(t1, t2, t1.length()-1, t2.length()-1);
    }
private int lcs(String a, String b, int i, int j) {
if (i < 0 || j < 0) return 0;
if (a.charAt(i) == b.charAt(j))
return 1 + lcs(a, b, i-1, j-1);
return Math.max(lcs(a,b,i-1,j), lcs(a,b,i,j-1));
    }
}

Python — Recursive

 class Solution:
def longestCommonSubsequence(self, t1: str, t2: str) -> int:
def lcs(i, j):
if i < 0 or j < 0: return 0 if t1[i] == t2[j]: return 1 + lcs(i-1, j-1)
return max(lcs(i-1, j), lcs(i, j-1))
return lcs(len(t1)-1, len(t2)-1)

Metric	Value
Time	O(2^(m+n))
Space	O(m+n)

Section Three · Approach 2

2D DP — O(m·n)

Build a (m+1)×(n+1) table. If characters match: dp[i][j] = dp[i-1][j-1] + 1. Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

💡 Mental model: Line up both strings on the edges of a grid — text1 down the rows, text2 across the columns. Each cell asks: "What's the best alignment up to this character in each string?" When characters match, it's like finding a matching puzzle piece — extend the diagonal by 1. When they don't, take the better of skipping a character from either string (look left or up).

Algorithm

Create dp[(m+1)][n+1] initialized to 0 (empty string has LCS 0 with anything).
For i from 1 to m, j from 1 to n:
If text1[i-1] == text2[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].

🎯 When to recognize this pattern:

"Longest/shortest common subsequence between two strings." The signal: two sequences, match characters while maintaining relative order.
This is THE classic 2D DP problem.
Variants: LC 583 (Delete Operations — LCS gives answer), LC 1092 (Shortest Common Supersequence), LC 72 (Edit Distance — three operations instead of match/skip).

Space optimization:

Since each row only depends on the previous row, you can use two 1D arrays (or even one with careful bookkeeping) to reduce space to O(min(m,n)).
For interviews, the full 2D table is clearer and sufficient.

Section Four · Trace

Visual Walkthrough

Trace for text1="abcde", text2="ace".

LCS — 2D DP Table (text1="abcde", text2="ace")

Section Five · Implementation

Code — Java & Python

Java — 2D DP

 class Solution {
public int longestCommonSubsequence(String t1, String t2) {
int m = t1.length(), n = t2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
                dp[i][j] = t1.charAt(i-1) == t2.charAt(j-1)
                    ? dp[i-1][j-1] + 1 // match → extend
: Math.max(dp[i-1][j], dp[i][j-1]); // skip one return dp[m][n];
    }
}

Python — 2D DP

 class Solution:
def longestCommonSubsequence(self, t1: str, t2: str) -> int:
        m, n = len(t1), len(t2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if t1[i-1] == t2[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]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	O(2^(m+n))	O(m+n)	Exponential — TLE
Memoized recursion	O(m·n)	O(m·n)	Top-down with memo table
2D DP ← optimal	O(m·n)	O(m·n)	Bottom-up; can optimize to O(min(m,n)) space

LCS vs LIS: LCS compares two sequences (2D DP). LIS is a single sequence (1D DP or binary search). However, LIS can be reduced to LCS in some formulations. Know both — they're the two most fundamental subsequence problems.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No common chars	`"abc", "xyz"`	All cells stay 0. Return 0.
Identical strings	`"abc", "abc"`	LCS = length of string. All diagonal matches.
One char each	`"a", "b"`	No match. Return 0.
One string is subsequence	`"abcde", "ace"`	LCS = shorter string length = 3.
Repeated chars	`"aaa", "aa"`	LCS = 2. All 'a's match; min length governs.

⚠ Common Mistake: Confusing subsequence with substring. A subsequence can skip characters (maintaining order), while a substring must be contiguous. LCS allows skipping. If you wrote dp[i][j] = dp[i-1][j-1]+1 only when chars match AND reset to 0 otherwise, you'd be solving Longest Common Substring instead.

← Back to DP — 2D problems

LearningTree

LC 1143 · Longest Common Subsequence — Solution & Explanation | DSA Guide