Difficulty: Medium2-D Dynamic Programming

Longest Common Subsequence

Problem in Plain English

Given two strings, find the length of the longest sequence of characters that appears in both strings in the same relative order. Characters may be skipped but never reordered.

Problem Statement

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

A subsequence is formed by deleting zero or more characters from a string without changing the relative order of the rest. For text1 = "abcde" and text2 = "ace", the answer is 3 because "ace" appears in both in the same order.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English letters.

Examples

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3

Choose a, c, and e at positions 0, 2, and 4 of abcde; ace supplies the same three characters in order. Length 3 reaches the shorter string length, so no longer answer is possible. The gaps show that this is a subsequence, not a substring.

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3

All three characters match in order without deleting anything. The answer cannot exceed either input length, so the whole string abc is optimal with length 3.

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0

There is no shared character at all. Only the empty subsequence appears in both strings, so its length 0 is the answer even though neither input is empty.

Example 4

Input: text1 = "abc", text2 = "bac"
Output: 2

Either ac or bc is shared in order. A length-3 answer would have to use every character of both strings, but their first two characters have opposite order, so 3 is impossible.

Example 5

Input: text1 = "a", text2 = "aaaa"
Output: 1

The single a can be used only once. Repeated matches in the second string do not create extra characters in the first.

Intuition

A subsequence preserves order but allows gaps. In abcde and ace, skip b and d while matching a, c, and e, giving length 3. For two remaining suffixes, matching heads can contribute one character and advance both positions. Different heads cannot both be the first matched pair, so try discarding one head or the other and keep the better length. Repeated suffix pairs motivate a table; the bottom-up version stores prefix lengths instead.

Approaches

Brute Force Recursion

Solution Details

Reveal Brute Force Recursion: intuition, complexity, and code

Intuition

Explore the match-or-skip recurrence directly on suffix positions. Matching heads can be used together, adding one and advancing both indices; different heads require comparing the two ways to skip one character. In Example 1, matching a leads to suffixes bcde and ce, where skipping b preserves the next c match. This exhaustive recursion repeats suffix states because it has no cache.

Step-by-Step Logic

Start dfs(0, 0) with indices into the original strings, returning zero whenever either index reaches its length. Avoid suffix slices so recursion stores only positions.
If the current heads match, return one plus dfs(i + 1, j + 1). Example 1 begins with a = a, so its root is 1 + dfs(1, 1), comparing bcde with ce.
If the heads differ, evaluate both skips and take the maximum. At (1, 1), b differs from c: compare dfs(2, 1) with dfs(1, 2).
Continue to the boundary and combine the results on return. The c match gives 1 + dfs(3, 2); d versus e chooses between skipping d (length 1) and exhausting text2 (length 0).
Return the root length. The branches under (1, 1) give 2 and 1, so the initial a contributes 1 + 2 = 3. Duplicate states in the trace are listed once with their multiplicities.

Why It Works

If either remaining string is empty, the answer is zero. When the heads match, an optimal solution can include that pair: if it uses one head with a later equal character, move that match to the two heads; if it uses neither, prepend the matching pair and improve it. Thus some optimum starts with those heads and its remainder is an optimum of the two shortened suffixes. When heads differ, no common subsequence pairs them; any alignment skips at least one head. The two recursive children cover those alternatives and taking the maximum chooses the best. Every call decreases remaining length, so induction proves the returned length is optimal.

Dry Run

Brute Force Recursion: variable states at each step
i	j	Rule and child values (unique states in first-call order)	Calls merged	Returned length
0	0	a=a; 1 + f(1,1)	1	3
1	1	b!=c; max(f(2,1)=2, f(1,2)=1)	1	2
2	1	c=c; 1 + f(3,2)	1	2
3	2	d!=e; max(f(4,2)=1, f(3,3)=0)	2	1
4	2	e=e; 1 + f(5,3)	2	1
5	3	empty suffix	2	0
3	3	empty suffix	2	0
1	2	b!=e; max(f(2,2)=1, f(1,3)=0)	1	1
2	2	c!=e; max(f(3,2)=1, f(2,3)=0)	1	1
2	3	empty suffix	1	0
1	3	empty suffix	1	0
root return	(0,0)	1 + f(1,1) = 1 + 2	repeated calls above merged explicitly	3

Complexity Analysis

Time Complexity

O(2^{m+n})

Space Complexity

O(m+n)

Let m and n be the nonempty input lengths. Each mismatching state has two children and every edge consumes at least one character, giving the exponential upper bound. At most m + n frames are live, with no memoization or suffix-string allocation. The Python method reserves enough recursion depth and restores the previous limit on exit; Java and JavaScript also require enough runtime stack for long paths (verification uses Java -Xss16m and Node --stack-size=16384). Identical length-1000 strings are linear, but general highly branching maximum inputs are infeasible here and belong to the table approach.

Code

Solution.java

1class Solution {2    public int longestCommonSubsequence(String text1, String text2) {3        return dfs(text1, text2, 0, 0);4    }5
6    private int dfs(String a, String b, int i, int j) {7        if (i == a.length() || j == b.length()) {8            return 0;9        }10        // Equal heads can begin an optimum; unmatched heads require both skips.11        if (a.charAt(i) == b.charAt(j)) {12            return 1 + dfs(a, b, i + 1, j + 1);13        }14        return Math.max(dfs(a, b, i + 1, j), dfs(a, b, i, j + 1));15    }16}

Hints

Hint 1

Compare the strings from one end and ask what must be true when the current characters match.

Hint 2

When current characters differ, at least one must be skipped before a matched pair can start; compare both skips rather than committing greedily.

Hint 3

Name the state after the two positions already consumed, then fill a grid where each cell reuses the cells above, left, and diagonally above-left.

Edge Cases

No shared characters, as in text1 = "abc" with text2 = "def", so the answer is 0.
One string is entirely a subsequence of the other, so the answer equals the shorter length.
Both strings share long repeated characters, which the recurrence handles without any special casing.
One character against a repeated run, such as a and aaaa, still contributes only one match.
Different order can shorten the answer despite equal character counts: abc and bac have length 2, not 3.

Common Mistakes and Interview Tips

Treating the problem as longest common substring and requiring contiguity, which undercounts answers like "ace" inside "abcde".
Using a greedy first-match scan, which can consume a character early and block a longer subsequence later.
Sizing the table as m by n instead of m + 1 by n + 1, which removes the zero base row and breaks the recurrence.
At a recursive match, advance both indices. Example 1 goes from (0,0) to (1,1), not (1,0).
Resetting mismatches to zero solves a substring problem; subsequences retain the better top or left value.
Treating the bottom-up prefix table as a suffix table and filling it backwards reads uncomputed dependencies.
In Python, creating rows with [[0] * columns] * rows aliases storage; each row must be allocated independently.
Interview tip: length computation and actual sequence reconstruction are different outputs. State the requested output and explain the recurrence before coding.

Key Takeaway

When the answer depends on two prefixes at once, index the state by both positions and let each cell combine its top, left, and diagonal neighbours.