Loading…

mediumDynamic ProgrammingLC #1143Frequently asked

Longest Common Subsequence

Q: How do you solve Longest Common Subsequence using the Plain Recursion — Compare from the Ends approach?

When to use it: Use it to derive the recurrence out loud, then immediately call out that it's exponential and needs memoisation. Never present it as the final answer. Define `lcs(i, j)` as the LCS length of `text1[0..i-1]` and `text2[0..j-1]`. Decide one character at a time, working from the back of each string. **Why we look at the ends.** Consider the *last* characters of the two prefixes. If they're equal, then there's an optimal LCS that *uses* this matched pair: pair them up, add 1, and recurse on the strings with both last characters removed — `1 + lcs(i-1, j-1)`. If they differ, that pair can't both be in the LCS, so at least one of those two characters is useless — we try removing the last char of the first string (`lcs(i-1, j)`) and removing the last char of the second (`lcs(i, j-1)`), and keep whichever yields more. **Why an empty prefix returns 0.** If either string has run out of characters, there's nothing left to match, so the LCS is length 0. That's the recursion's base case and the source of the table's zero row/column later. **Why we don't ship this.** The mismatch branch forks into two subproblems, and those subproblems overlap massively — `lcs(i-1, j)` and `lcs(i, j-1)` both eventually call `lcs(i-1, j-1)`. Recomputing the same `(i, j)` pair over and over makes the naive tree exponential. The fix is to *remember* each `(i, j)` result once computed — which turns this exact recurrence into the O(m·n) DP below. Time complexity: O(2^(m+n)). Space complexity: O(m+n).

Q: How do you solve Longest Common Subsequence using the 2D DP Table — Bottom-Up Prefix Grid (Optimal) approach?

When to use it: The answer they want. Frame it as 'memoise the recursion into a (m+1)×(n+1) grid and fill it bottom-up.' Allocate `dp[m+1][n+1]` where `dp[i][j]` is the LCS length of the first `i` characters of `text1` and the first `j` of `text2`. Row 0 and column 0 are all zeros (empty prefix). Fill the rest in increasing order of `i` and `j`. **Why the table mirrors the recursion exactly.** Each cell answers the same question `lcs(i, j)` did — but because we fill in increasing `i, j`, every value the recurrence needs (`dp[i-1][j-1]`, `dp[i-1][j]`, `dp[i][j-1]`) is already sitting in the table. So the exponential blow-up disappears: each `(i, j)` pair is computed once. The table *is* the memo. **Why the diagonal means 'match'.** When `text1[i-1] == text2[j-1]`, we extend the best alignment of the two shorter prefixes by this matched pair: `dp[i][j] = dp[i-1][j-1] + 1`. The diagonal cell represents 'both strings one character shorter', so adding 1 records that we consumed a character from each and gained a match. **Why the mismatch takes a max of above and left.** If the current characters differ, the LCS can't use both, so we must skip one: `dp[i-1][j]` is 'ignore `text1`'s current char', `dp[i][j-1]` is 'ignore `text2`'s'. We keep the larger — exactly the recursion's mismatch branch, now read from already-filled neighbours. **Why the indices are offset by one.** The `+1` table dimension lets row/column 0 be the empty-prefix base case without special-casing, which is why we compare `text1[i-1]` against `text2[j-1]` — table index `i` corresponds to string index `i-1`. The answer lives at `dp[m][n]`. Time complexity: O(m·n). Space complexity: O(m·n).

LCPractice

Dynamic Programming · 12 of 44 · 9 min

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 string with some characters (can be none) deleted **without changing the relative order** of the remaining characters.

A common subsequence of two strings is a subsequence that is common to both strings.

In plain English

Given two strings, find how many characters you can pick from both — in the same relative order in each — such that the picked characters are identical. You're not looking for a contiguous block; gaps are allowed as long as order is preserved.

Examples

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3
Note: The longest common subsequence is "ace", length 3 — note 'a', 'c', 'e' are not contiguous in "abcde".

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3
Note: Identical strings — the entire string is the common subsequence.

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0
Note: No shared characters, so there is no common subsequence.

Constraints

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of lowercase English characters only
Order of characters must be preserved (subsequence, not subset)
Characters need not be contiguous

Clarifying questions4First question: Subsequence or substring — do the characters have to be contiguous?Explore questions

Q1.Subsequence or substring — do the characters have to be contiguous?
Subsequence: order must be preserved but the characters need not be adjacent. 'ace' is a subsequence of 'abcde'. This is the crux of the problem.
Q2.Do I return the length or the actual subsequence?
Just the length for LeetCode 1143. Reconstructing the string is a common follow-up and needs an extra backtrack over the table.
Q3.Can the strings be empty?
The constraints say length ≥ 1, but the DP base case (an empty prefix shares nothing) handles length 0 gracefully — return 0.
Q4.Is the matching case-sensitive?
Yes — only lowercase letters appear, so 'a' and 'A' never collide here, but in general you'd clarify casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the length of the longest subsequence common to two strings (characters in order, not necessarily contiguous). Compare the strings character by character: when two characters match, take the diagonal +1; when they don't, take the better of dropping one character from either string. That's the canonical 2D DP — dp[i][j] = match ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]) — in O(m·n) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can model a problem over *two* inputs as a 2D DP — define dp[i][j] over prefixes, get the match/mismatch transition right, and reason about why the diagonal represents 'both characters used'.

Where candidates slip

Confusing subsequence with substring (resetting to 0 on a mismatch), or mixing up the 1-based DP indices with the 0-based string indices and reading the wrong characters.

How to stand out

Derive the recurrence from the brute-force recursion first, then mention you can roll the table to two rows for O(min(m,n)) space, and note the same grid solves Edit Distance with a tweaked transition.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Plain Recursion — Compare from the Ends	`O(2^(m+n))`	`O(m+n)`	Use it to derive the recurrence out loud, then immediately call out that it's exponential and needs memoisation. Never present it as the final answer.	Read
2	2D DP Table — Bottom-Up Prefix Grid (Optimal)Optimal	`O(m·n)`	`O(m·n)`	The answer they want. Frame it as 'memoise the recursion into a (m+1)×(n+1) grid and fill it bottom-up.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLongest common subsequence of A, BNeed to derive or already know it?Deriving from scratchProduction answerExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Plain Recursion — Compare from the Ends

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

Use it to derive the recurrence out loud, then immediately call out that it's exponential and needs memoisation. Never present it as the final answer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the last character of each string. If they're equal, that character can be part of the LCS — what's left to solve?

2Hint 2Explore hint

If the last characters differ, at least one of them isn't in the LCS. Try dropping the last char of A, then of B, and keep the better result.

3Hint 3Explore hint

Write lcs(i, j) over prefixes: match → 1 + lcs(i-1, j-1); mismatch → max(lcs(i-1, j), lcs(i, j-1)); empty prefix → 0.

A · Core idea

Define lcs(i, j) as the LCS length of text1[0..i-1] and text2[0..j-1]. Decide one character at a time, working from the back of each string.

Why we look at the ends. Consider the last characters of the two prefixes. If they're equal, then there's an optimal LCS that uses this matched pair: pair them up, add 1, and recurse on the strings with both last characters removed — 1 + lcs(i-1, j-1). If they differ, that pair can't both be in the LCS, so at least one of those two characters is useless — we try removing the last char of the first string (lcs(i-1, j)) and removing the last char of the second (lcs(i, j-1)), and keep whichever yields more.

Why an empty prefix returns 0. If either string has run out of characters, there's nothing left to match, so the LCS is length 0. That's the recursion's base case and the source of the table's zero row/column later.

Why we don't ship this. The mismatch branch forks into two subproblems, and those subproblems overlap massively — lcs(i-1, j) and lcs(i, j-1) both eventually call lcs(i-1, j-1). Recomputing the same (i, j) pair over and over makes the naive tree exponential. The fix is to remember each (i, j) result once computed — which turns this exact recurrence into the O(m·n) DP below.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

text1 = "ab", text2 = "azb"

lcs(2,3)

'b' == 'b' → 1 + lcs(1,2)

Statematched 'b'

Final result2

C · Code with teaching comments

Reference implementation previewpublic int longestCommonSubsequence(String text1, String text2) { return lcs(text1, text2, text1.length(), text2.length()); } private int lcs(String a, String b, int i, int j) {Explore the full code

solution.javaJava

Plain Recursion — Compare from the Ends — reference

4 teaching notes

1
public int longestCommonSubsequence(String text1, String text2) {
2
    return lcs(text1, text2, text1.length(), text2.length());
3
}
4
 
5
private int lcs(String a, String b, int i, int j) {
6
    // Either prefix empty → nothing to match → base case 0.
7
    if (i == 0 || j == 0) return 0;
8
    // i-1 / j-1 convert 1-based prefix lengths to 0-based string indices.
9
    if (a.charAt(i - 1) == b.charAt(j - 1)) {
10
        // Match: count this char and shrink BOTH prefixes — the diagonal move.
11
        return 1 + lcs(a, b, i - 1, j - 1);
12
    }
13
    // Mismatch: drop a char from one string or the other, keep the better — this
14
    // branching is what makes it exponential.
15
    return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1));
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(2^(m+n)) timeO(m+n) spaceOpen the invariant and proofExplore the proof

The whole problem hinges on one decision repeated: 'do the current ends match?' Match collapses both strings by one (the diagonal move); mismatch advances one string only (a horizontal or vertical move). Seeing the recursion as movement on a grid is the bridge to the table — the table is literally the memo of this function.

ComplexityO(2^(m+n)) time, O(m+n) space — Each mismatch spawns two recursive calls and the recursion depth is up to m+n, so without memoisation the call tree is exponential. The only memory is the recursion stack, O(m+n) deep.

E · Edge cases and pitfalls5text1 = "abc", text2 = "def" — Every comparison mismatches and every branch eventually hits an empty prefix → returns 0.Explore edge cases

Edge cases handled

text1 = "abc", text2 = "def"Every comparison mismatches and every branch eventually hits an empty prefix → returns 0.
text1 = "a", text2 = "a"Single match at lcs(1,1) → 1 + lcs(0,0) = 1.

Pitfalls

Indexing the strings with i and j directly instead of i-1 / j-1 — off-by-one and out-of-bounds.
Resetting to 0 on a mismatch (that's substring logic) instead of taking the max of the two skips.
Presenting this as a final solution — without memoisation it TLEs on length-1000 inputs.

03.2

Approach 2 of 2 · Optimal

2D DP Table — Bottom-Up Prefix Grid (Optimal)

TimeO(m·n)SpaceO(m·n)

The answer they want. Frame it as 'memoise the recursion into a (m+1)×(n+1) grid and fill it bottom-up.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Take the recursive lcs(i, j) and store every answer in a table indexed by (i, j) so you never recompute a pair.

2Hint 2Explore hint

Make the table (m+1)×(n+1) so row 0 and column 0 represent empty prefixes and are all zeros — the base case baked in.

3Hint 3Explore hint

Fill it in increasing i, j. Each cell uses the diagonal (on a match) or the cell above/left (on a mismatch), all already computed.

A · Core idea

Allocate dp[m+1][n+1] where dp[i][j] is the LCS length of the first i characters of text1 and the first j of text2. Row 0 and column 0 are all zeros (empty prefix). Fill the rest in increasing order of i and j.

Why the table mirrors the recursion exactly. Each cell answers the same question lcs(i, j) did — but because we fill in increasing i, j, every value the recurrence needs (dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) is already sitting in the table. So the exponential blow-up disappears: each (i, j) pair is computed once. The table is the memo.

Why the diagonal means 'match'. When text1[i-1] == text2[j-1], we extend the best alignment of the two shorter prefixes by this matched pair: dp[i][j] = dp[i-1][j-1] + 1. The diagonal cell represents 'both strings one character shorter', so adding 1 records that we consumed a character from each and gained a match.

Why the mismatch takes a max of above and left. If the current characters differ, the LCS can't use both, so we must skip one: dp[i-1][j] is 'ignore text1's current char', dp[i][j-1] is 'ignore text2's'. We keep the larger — exactly the recursion's mismatch branch, now read from already-filled neighbours.

Why the indices are offset by one. The +1 table dimension lets row/column 0 be the empty-prefix base case without special-casing, which is why we compare text1[i-1] against text2[j-1] — table index i corresponds to string index i-1. The answer lives at dp[m][n].

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

text1 = "ace", text2 = "abcde"

Array state

cols a,b

'c' ≠ 'a','b' → max(up, left) stays 1

[0]

[1]

j ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

2D DP Table — Bottom-Up Prefix Grid (Optimal) — optimal

5 teaching notes

1
public int longestCommonSubsequence(String text1, String text2) {
2
    int m = text1.length(), n = text2.length();
3
    // The +1 border (row 0, col 0 = 0) encodes the empty-prefix base case so the loops
4
    // never special-case it.
5
    int[][] dp = new int[m + 1][n + 1];
6
    for (int i = 1; i <= m; i++) {
7
        for (int j = 1; j <= n; j++) {
8
            // Table index i maps to string index i-1 — the source of every off-by-one
9
            // bug here.
10
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
11
                // Match: extend the diagonal (both prefixes one shorter) by this
12
                // matched character.
13
                dp[i][j] = dp[i - 1][j - 1] + 1;
14
            } else {
15
                // Mismatch: best of skipping text1's char (up) or text2's char (left).
16
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
17
            }
18
        }
19
    }
20
    // Full strings vs full strings — the bottom-right cell is the answer.
21
    return dp[m][n];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

The deep idea is that a two-input problem becomes a plane of subproblems, and filling that plane in dependency order replaces recursion with three array reads. Internalise the cell picture — diagonal-plus-one on a match, max-of-neighbours on a mismatch — and Edit Distance, Delete Operation, and Shortest Common Supersequence are all the same grid with a different per-cell rule.

ComplexityO(m·n) time, O(m·n) space — There are (m+1)·(n+1) cells and each is filled in O(1) from three neighbours, so time is O(m·n). The full table is stored, so space is O(m·n) — reducible to O(min(m,n)) by keeping two rows.

E · Edge cases and pitfalls5text1 = "abc", text2 = "abc" — Every diagonal matches; dp climbs 1,2,3 down the diagonal → dp[3][3] = 3.Explore edge cases

Edge cases handled

text1 = "abc", text2 = "abc"Every diagonal matches; dp climbs 1,2,3 down the diagonal → dp[3][3] = 3.
text1 = "abc", text2 = "def"No character ever matches; max(up,left) stays 0 across the whole grid → returns 0.

Pitfalls

Sizing the table m×n instead of (m+1)×(n+1) — you lose the zero base row/column and mishandle the first characters.
Treating a mismatch like a substring problem and resetting dp[i][j] to 0 — that computes longest common *substring*.
Reading dp[i][j] off the diagonal on a mismatch — only matches use the diagonal.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Substring reset on mismatch

Resetting dp[i][j] to 0 when characters differ computes the longest common *contiguous* substring, not the subsequence — a different and smaller answer.

Explore the code comparison

Don't write this

if (text1.charAt(i-1) == text2.charAt(j-1))
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = 0; // substring logic — WRONG for subsequence

Write this instead

if (text1.charAt(i-1) == text2.charAt(j-1))
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

Off-by-one between table and string indices

Table cell dp[i][j] covers prefixes of length i and j, so the characters being compared are at string indices i-1 and j-1, not i and j.

Explore the code comparison

Don't write this

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if text1[i] == text2[j]:  # IndexError / wrong chars
            dp[i][j] = dp[i-1][j-1] + 1

Write this instead

for i in range(1, m + 1):
    for j in range(1, n + 1):
        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])

Naive recursion without memoisation

The mismatch branch forks into two overlapping subproblems; recomputing them is exponential and TLEs on length-1000 strings.

Explore the code comparison

Don't write this

def lcs(i, j):
    if i == 0 or j == 0: return 0
    if a[i-1] == b[j-1]: return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))  # recomputes same (i,j) endlessly

Write this instead

from functools import lru_cache
@lru_cache(maxsize=None)
def lcs(i, j):
    if i == 0 or j == 0: return 0
    if a[i-1] == b[j-1]: return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-string 2D DP — align by prefixes

Code pattern to memorize

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1     # match → diagonal + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one char

Rules to remember

1State is (prefix of A, prefix of B) — dp[i][j] is the LCS of the first i chars of A and first j of B.
2On a match, jump to the diagonal dp[i-1][j-1] + 1: both characters are consumed and contribute 1.
3On a mismatch, take max(dp[i-1][j], dp[i][j-1]) — you must drop a character from one string, so try both and keep the better.
4Use a (m+1)×(n+1) table with row 0 and column 0 as zeros: an empty string shares nothing, the natural base case.
5Subsequence ≠ substring — characters must keep order but need not be contiguous, which is exactly why the 'skip a char' branch exists.

Use this pattern when

Two sequences (strings/arrays) and you're aligning, matching, or editing one into the other
Answer depends on comparing a prefix of one input against a prefix of the other
'Longest common', 'edit distance', 'minimum deletions to make equal' style phrasing
Order matters but contiguity does not — the hallmark of subsequence DP

Choose another pattern when

Need a contiguous match → that's Longest Common *Substring* (reset to 0 on mismatch)
Only one sequence → likely a 1D DP (LIS, House Robber), not a 2D grid
You need the actual subsequence string, not just its length → still DP but add a backtrack pass
Sequences are huge and only length matters → consider Hirschberg's O(n) space, not full table

Interview takeaway

LCS is the archetype of two-string DP: index into both strings, branch on match vs mismatch, and the recurrence falls out. Once you see the prefix-vs-prefix grid, Edit Distance, Shortest Common Supersequence, and Delete Operation for Two Strings are all the same machine with a different per-cell formula.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical two-string 2D DP — index over prefixes of both inputs, branch on match (diagonal + 1) vs mismatch (max of neighbours). Recognise it for any 'align / edit / longest common' question over two sequences; Edit Distance, Shortest Common Supersequence, and Longest Palindromic Subsequence are the same grid with a tweaked per-cell rule.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Edit Distance
Same prefix grid; on a mismatch take 1 + min(insert, delete, replace) instead of a plain max.
Delete Operation for Two Strings
Coming soon
Answer is m + n − 2·LCS — the chars outside the LCS must be deleted from each side.
Shortest Common Supersequence
Coming soon
Build the LCS table, then walk it backwards to weave both strings around the shared subsequence.
Longest Palindromic Subsequence
It's LCS of the string with its own reverse — the same table, one input reversed.

Same pattern

←

Unique Paths

Continue · Next problem

Maximum Product Subarray

mediumDynamic ProgrammingLC #1143Frequently asked

Longest Common Subsequence

LCPractice

Dynamic Programming · 12 of 44 · 9 min

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 string with some characters (can be none) deleted **without changing the relative order** of the remaining characters.

A common subsequence of two strings is a subsequence that is common to both strings.

In plain English

Examples

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3
Note: The longest common subsequence is "ace", length 3 — note 'a', 'c', 'e' are not contiguous in "abcde".

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3
Note: Identical strings — the entire string is the common subsequence.

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0
Note: No shared characters, so there is no common subsequence.

Constraints

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of lowercase English characters only
Order of characters must be preserved (subsequence, not subset)
Characters need not be contiguous

Clarifying questions4First question: Subsequence or substring — do the characters have to be contiguous?Explore questions

Q1.Subsequence or substring — do the characters have to be contiguous?
Subsequence: order must be preserved but the characters need not be adjacent. 'ace' is a subsequence of 'abcde'. This is the crux of the problem.
Q2.Do I return the length or the actual subsequence?
Just the length for LeetCode 1143. Reconstructing the string is a common follow-up and needs an extra backtrack over the table.
Q3.Can the strings be empty?
The constraints say length ≥ 1, but the DP base case (an empty prefix shares nothing) handles length 0 gracefully — return 0.
Q4.Is the matching case-sensitive?
Yes — only lowercase letters appear, so 'a' and 'A' never collide here, but in general you'd clarify casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Confusing subsequence with substring (resetting to 0 on a mismatch), or mixing up the 1-based DP indices with the 0-based string indices and reading the wrong characters.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Plain Recursion — Compare from the Ends	`O(2^(m+n))`	`O(m+n)`	Use it to derive the recurrence out loud, then immediately call out that it's exponential and needs memoisation. Never present it as the final answer.	Read
2	2D DP Table — Bottom-Up Prefix Grid (Optimal)Optimal	`O(m·n)`	`O(m·n)`	The answer they want. Frame it as 'memoise the recursion into a (m+1)×(n+1) grid and fill it bottom-up.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Plain Recursion — Compare from the Ends

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

Use it to derive the recurrence out loud, then immediately call out that it's exponential and needs memoisation. Never present it as the final answer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the last character of each string. If they're equal, that character can be part of the LCS — what's left to solve?

2Hint 2Explore hint

If the last characters differ, at least one of them isn't in the LCS. Try dropping the last char of A, then of B, and keep the better result.

3Hint 3Explore hint

Write lcs(i, j) over prefixes: match → 1 + lcs(i-1, j-1); mismatch → max(lcs(i-1, j), lcs(i, j-1)); empty prefix → 0.

A · Core idea

Define lcs(i, j) as the LCS length of text1[0..i-1] and text2[0..j-1]. Decide one character at a time, working from the back of each string.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

text1 = "ab", text2 = "azb"

lcs(2,3)

'b' == 'b' → 1 + lcs(1,2)

Statematched 'b'

Final result2

C · Code with teaching comments

solution.javaJava

Plain Recursion — Compare from the Ends — reference

4 teaching notes

1
public int longestCommonSubsequence(String text1, String text2) {
2
    return lcs(text1, text2, text1.length(), text2.length());
3
}
4
 
5
private int lcs(String a, String b, int i, int j) {
6
    // Either prefix empty → nothing to match → base case 0.
7
    if (i == 0 || j == 0) return 0;
8
    // i-1 / j-1 convert 1-based prefix lengths to 0-based string indices.
9
    if (a.charAt(i - 1) == b.charAt(j - 1)) {
10
        // Match: count this char and shrink BOTH prefixes — the diagonal move.
11
        return 1 + lcs(a, b, i - 1, j - 1);
12
    }
13
    // Mismatch: drop a char from one string or the other, keep the better — this
14
    // branching is what makes it exponential.
15
    return Math.max(lcs(a, b, i - 1, j), lcs(a, b, i, j - 1));
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(2^(m+n)) timeO(m+n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5text1 = "abc", text2 = "def" — Every comparison mismatches and every branch eventually hits an empty prefix → returns 0.Explore edge cases

Edge cases handled

text1 = "abc", text2 = "def"Every comparison mismatches and every branch eventually hits an empty prefix → returns 0.
text1 = "a", text2 = "a"Single match at lcs(1,1) → 1 + lcs(0,0) = 1.

Pitfalls

Indexing the strings with i and j directly instead of i-1 / j-1 — off-by-one and out-of-bounds.
Resetting to 0 on a mismatch (that's substring logic) instead of taking the max of the two skips.
Presenting this as a final solution — without memoisation it TLEs on length-1000 inputs.

03.2

Approach 2 of 2 · Optimal

2D DP Table — Bottom-Up Prefix Grid (Optimal)

TimeO(m·n)SpaceO(m·n)

The answer they want. Frame it as 'memoise the recursion into a (m+1)×(n+1) grid and fill it bottom-up.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Take the recursive lcs(i, j) and store every answer in a table indexed by (i, j) so you never recompute a pair.

2Hint 2Explore hint

Make the table (m+1)×(n+1) so row 0 and column 0 represent empty prefixes and are all zeros — the base case baked in.

3Hint 3Explore hint

Fill it in increasing i, j. Each cell uses the diagonal (on a match) or the cell above/left (on a mismatch), all already computed.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

text1 = "ace", text2 = "abcde"

Array state

cols a,b

'c' ≠ 'a','b' → max(up, left) stays 1

[0]

[1]

j ↓

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

2D DP Table — Bottom-Up Prefix Grid (Optimal) — optimal

5 teaching notes

1
public int longestCommonSubsequence(String text1, String text2) {
2
    int m = text1.length(), n = text2.length();
3
    // The +1 border (row 0, col 0 = 0) encodes the empty-prefix base case so the loops
4
    // never special-case it.
5
    int[][] dp = new int[m + 1][n + 1];
6
    for (int i = 1; i <= m; i++) {
7
        for (int j = 1; j <= n; j++) {
8
            // Table index i maps to string index i-1 — the source of every off-by-one
9
            // bug here.
10
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
11
                // Match: extend the diagonal (both prefixes one shorter) by this
12
                // matched character.
13
                dp[i][j] = dp[i - 1][j - 1] + 1;
14
            } else {
15
                // Mismatch: best of skipping text1's char (up) or text2's char (left).
16
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
17
            }
18
        }
19
    }
20
    // Full strings vs full strings — the bottom-right cell is the answer.
21
    return dp[m][n];
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5text1 = "abc", text2 = "abc" — Every diagonal matches; dp climbs 1,2,3 down the diagonal → dp[3][3] = 3.Explore edge cases

Edge cases handled

text1 = "abc", text2 = "abc"Every diagonal matches; dp climbs 1,2,3 down the diagonal → dp[3][3] = 3.
text1 = "abc", text2 = "def"No character ever matches; max(up,left) stays 0 across the whole grid → returns 0.

Pitfalls

Sizing the table m×n instead of (m+1)×(n+1) — you lose the zero base row/column and mishandle the first characters.
Treating a mismatch like a substring problem and resetting dp[i][j] to 0 — that computes longest common *substring*.
Reading dp[i][j] off the diagonal on a mismatch — only matches use the diagonal.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Substring reset on mismatch

Resetting dp[i][j] to 0 when characters differ computes the longest common *contiguous* substring, not the subsequence — a different and smaller answer.

Explore the code comparison

Don't write this

if (text1.charAt(i-1) == text2.charAt(j-1))
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = 0; // substring logic — WRONG for subsequence

Write this instead

if (text1.charAt(i-1) == text2.charAt(j-1))
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

Off-by-one between table and string indices

Table cell dp[i][j] covers prefixes of length i and j, so the characters being compared are at string indices i-1 and j-1, not i and j.

Explore the code comparison

Don't write this

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if text1[i] == text2[j]:  # IndexError / wrong chars
            dp[i][j] = dp[i-1][j-1] + 1

Write this instead

for i in range(1, m + 1):
    for j in range(1, n + 1):
        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])

Naive recursion without memoisation

The mismatch branch forks into two overlapping subproblems; recomputing them is exponential and TLEs on length-1000 strings.

Explore the code comparison

Don't write this

def lcs(i, j):
    if i == 0 or j == 0: return 0
    if a[i-1] == b[j-1]: return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))  # recomputes same (i,j) endlessly

Write this instead

from functools import lru_cache
@lru_cache(maxsize=None)
def lcs(i, j):
    if i == 0 or j == 0: return 0
    if a[i-1] == b[j-1]: return 1 + lcs(i-1, j-1)
    return max(lcs(i-1, j), lcs(i, j-1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-string 2D DP — align by prefixes

Code pattern to memorize

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1     # match → diagonal + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one char

Rules to remember

1State is (prefix of A, prefix of B) — dp[i][j] is the LCS of the first i chars of A and first j of B.
2On a match, jump to the diagonal dp[i-1][j-1] + 1: both characters are consumed and contribute 1.
3On a mismatch, take max(dp[i-1][j], dp[i][j-1]) — you must drop a character from one string, so try both and keep the better.
4Use a (m+1)×(n+1) table with row 0 and column 0 as zeros: an empty string shares nothing, the natural base case.
5Subsequence ≠ substring — characters must keep order but need not be contiguous, which is exactly why the 'skip a char' branch exists.

Use this pattern when

Two sequences (strings/arrays) and you're aligning, matching, or editing one into the other
Answer depends on comparing a prefix of one input against a prefix of the other
'Longest common', 'edit distance', 'minimum deletions to make equal' style phrasing
Order matters but contiguity does not — the hallmark of subsequence DP

Choose another pattern when

Need a contiguous match → that's Longest Common *Substring* (reset to 0 on mismatch)
Only one sequence → likely a 1D DP (LIS, House Robber), not a 2D grid
You need the actual subsequence string, not just its length → still DP but add a backtrack pass
Sequences are huge and only length matters → consider Hirschberg's O(n) space, not full table

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Edit Distance
Same prefix grid; on a mismatch take 1 + min(insert, delete, replace) instead of a plain max.
Delete Operation for Two Strings
Coming soon
Answer is m + n − 2·LCS — the chars outside the LCS must be deleted from each side.
Shortest Common Supersequence
Coming soon
Build the LCS table, then walk it backwards to weave both strings around the shared subsequence.
Longest Palindromic Subsequence
It's LCS of the string with its own reverse — the same table, one input reversed.

Same pattern

←

Unique Paths

Continue · Next problem

Maximum Product Subarray