What is the brute force approach and complexity for Longest Common Subsequence?

Compare the last letters: a match is used; otherwise drop one and recurse with time complexity O(2^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Longest Common Subsequence?

Keep only the row above and the current row; same rule, less memory with optimal time complexity O(N · M) and space complexity O(min(N, M)).

How do you identify the pattern for Longest Common Subsequence?

Look for key signals in the prompt: "subsequence (letters can be skipped, order kept)" indicates Gaps are allowed, so the answer is not a run of neighbours. That makes it LCS, not a substring.; "common to both strings" indicates Two strings and one answer: compare prefixes of both at once with a table dp[i][j].; "return the length" indicates We need a count, not the letters, so each cell stores one number..

Longest Common Subsequence

Medium·LeetCode #1143Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP — Strings (LCS: match → diagonal + 1, else max of the two skips)

Complexity:O(2^(N + M))→O(N · M)

Key Insight

Row i only reads row i − 1 and the cell just left of it in row i. So two rows are enough: one for the row above and one being filled. After each letter of text1, the new row becomes the row above. Put the shorter string along the row, so each row is as short as possible.

Core Validity Invariant

Filling row by row, from left to right, means each cell reads only finished cells, so dp[i][j] is correct the moment it is written.

Problem

You are given two strings text1 and text2. Find the length of the longest common subsequence: a string you can make from both strings by deleting some letters (or none) and keeping the rest in order. Return that length. If the strings share no letter, return 0.

Input

Two strings, text1 and text2.

Output

The length of the longest string that is a subsequence of both.

Example 1

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

Output: 3

ace is in both strings: delete b and d from abcde. No longer string is shared, so the answer is 3.

Example 2

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

Output: 3

The whole string is shared.

Example 3

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

Output: 0

The strings share no letters.

Constraints

• 1 ≤ text1.length, text2.length ≤ 1000
• Lowercase English letters only.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Does a common subsequence need the same position in both strings, or only the same order of letters?
2.
If I look at the last letter of each string, what choices do I have for that pair?
3.
Do I have to use the last letter of text1? Can I skip it and still have a valid answer?
4.
If the last letters match, how does that change the question about the shorter strings?
5.
What is the answer when one of the strings is empty?

Brute force approach

Idea

Let lcs(i, j) be the answer for the first i letters of text1 and the first j letters of text2. If the last letters match (text1[i−1] = text2[j−1]), a match is always safe to use: 1 + lcs(i−1, j−1). If they differ, at most one of them can be used, so take the better of lcs(i−1, j) (drop text1's last letter) and lcs(i, j−1) (drop text2's last letter).

Thinking process

1
Take text1 = abcde and text2 = ace, and start with lcs(5, 3). The last letters are e and e, which match. So the answer is 1 + lcs(4, 2), where lcs(4, 2) is the answer for abcd and ac.
2
lcs(4, 2): the last letters are d and c, which differ. Drop d: lcs(3, 2) = 2, because abc and ac share ac. Drop c: lcs(4, 1) = 1, because abcd and a share one letter. The better is 2, so lcs(4, 2) = 2 and lcs(5, 3) = 1 + 2 = 3.
3
Every call is one pair (i, j). A mismatch makes two calls, and both can reach the same smaller pair. For abcde and ace the brute force makes 15 calls, and 2 of them solve a pair that was already solved on another branch.
4
When i or j reaches 0, one string is empty and nothing is shared, so the answer is 0. That is the stopping rule.

Visual

Each circle is one call (i, j): the first i letters of text1 and the first j letters of text2. Edge labels show the letter used (+) or dropped (−). Orange = a pair already solved on another branch.

Brute force: recursion on (i, j)text1 = "abcde", text2 = "ace"step 1/25

calls

text1

▲a

text2

▲b

State

i: 5
j: 3
calls: 1
repeated calls: 0

Compare e and e

Compare the last letters: e and e.

Code & Implementation

brute.cpp

class Solution {
    // lcs(i, j): the answer for the first i letters of text1 and the first j letters of text2.
    int lcs(const string& text1, const string& text2, int i, int j) {
        if (i == 0 || j == 0) return 0;                       // one side is empty: nothing to share
        if (text1[i - 1] == text2[j - 1])                      // last letters match: use them
            return 1 + lcs(text1, text2, i - 1, j - 1);
        // They differ: at most one of the two last letters is used, so try dropping each one.
        return max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));
    }

public:
    int longestCommonSubsequence(string text1, string text2) {
        return lcs(text1, text2, text1.size(), text2.size());
    }
};

Complexity

Time O(2^(N + M))Space O(N + M)

Each call either moves both indexes (a match) or moves one of them (a mismatch), so the recursion is at most N + M levels deep. A mismatch makes two calls, so there are at most 2^(N + M) calls. The space is just the recursion depth, N + M.

Better approach

Why brute force is slow

The brute force solves the same pair (i, j) again on every branch that reaches it. Each mismatch makes two calls, so the work grows exponentially with the length of the strings.

What repeated work are we doing?

The same pair is reached by many different paths, and each time its whole subtree is worked out again. For abcde and ace, 2 of the 15 calls are for a pair already solved elsewhere.

What information can we reuse?

A cell dp[i][j] reads only three cells: above, to the left, and diagonal. Once it is written it never changes, so any pair can be looked up in O(1).

New approach

Idea

Fill a table dp[i][j] with the same rule as the brute force, one row at a time. Each cell is worked out once, from three cells that are already in the table, so no pair is solved twice.

Thinking process

1
The brute force reaches the same pair (i, j) from several branches. A table gives each pair one fixed cell, so we write its answer down the first time we need it.
2
Row 0 and column 0 are the empty prefixes, so they are all 0.
3
Cell dp[3][2] is for abc and ac. The last letters c and c match, so dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2.
4
Cell dp[4][2] is for abcd and ac. The last letters d and c differ, so dp[4][2] = max(dp[3][2], dp[4][1]) = max(2, 1) = 2.
5
The bottom-right cell dp[5][3] = 3 is the answer for the two whole strings.

Visual

Rows are the letters of text1, columns the letters of text2 (∅ = empty prefix). Blue = the cells read. Green = filled. Purple = the answer.

The full LCS tabletext1 = "abcde", text2 = "ace"step 1/17

dp[i][j]

∅

text1

text2

State

rows: 0 … 5
columns: 0 … 3

Start: row 0 and column 0 are the empty prefixes, so they are 0

dp[i][j] is the LCS of the first i letters of text1 and the first j letters of text2. Every cell is filled once.

Code & Implementation

better.cpp

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        // dp[i][j] = LCS of the first i letters of text1 and the first j letters of text2.
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;                 // match: extend the diagonal
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);      // no match: drop one letter
            }
        }
        return dp[n][m];
    }
};

Complexity

Time O(N · M)Space O(N · M)

The table has (N + 1) · (M + 1) cells, and each cell is one comparison and at most one addition. The table keeps every row, which is why the space is O(N · M).

Optimized approach

Idea

Start from brute force

The brute force answers lcs(i, j) many times. Its calls form a tree that reaches the same pair from many branches.

Find the repeated work

A mismatch makes two calls, and both can lead to the same smaller pairs. Without memory, the same answers are worked out again and again.

Define the state — what variables do I need?

dp[i][j]: The LCS of the first i letters of text1 and the first j letters of text2. Row 0 and column 0 are 0 (an empty string shares nothing).
i, j: How many letters of each string are in play. The letters being compared are text1[i−1] and text2[j−1].
prev, cur: The optimal keeps two rows: prev is row i − 1 (only read) and cur is row i (being filled). They swap after each letter of text1.

Define validity

Filling row by row, from left to right, means each cell reads only finished cells, so dp[i][j] is correct the moment it is written.

Define the transitions — when does each pointer move, and why is it safe?

text1[i−1] = text2[j−1]

dp[i][j] = dp[i−1][j−1] + 1

The shared letter can end a common subsequence, and the rest is the best answer for the two shorter prefixes.

the two letters differ

dp[i][j] = max(dp[i−1][j], dp[i][j−1])

At most one of the two last letters can end the shared sequence, so drop one of them and keep the better answer.

before the loops

row 0 and column 0 are 0

An empty string shares no letters with anything.

What does the current window add to the answer?

The answer for the two whole strings is the last cell, dp[N][M]. The two-row version gives the same value, because each row only needs the row before it.

Code & Implementation

optimal.cpp

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // Keep the shorter string as the row length, so each row is as short as possible.
        if (text2.size() > text1.size()) swap(text1, text2);
        int m = text2.size();
        vector<int> prev(m + 1, 0);   // the row for the letters of text1 read so far, minus one
        vector<int> cur(m + 1, 0);    // the row being filled now
        for (char x : text1) {
            for (int j = 1; j <= m; j++) {
                if (x == text2[j - 1])
                    cur[j] = prev[j - 1] + 1;                    // match: diagonal + 1
                else
                    cur[j] = max(prev[j], cur[j - 1]);           // no match: the row above, or the cell to the left
            }
            swap(prev, cur);   // this row is the "row above" for the next letter of text1
        }
        return prev[m];
    }
};

Complexity

Time O(N · M)Space O(min(N, M))

Every pair is still visited once, so the time is N · M. Only two rows of min(N, M) + 1 values are kept, so the space is O(min(N, M)). The code swaps the strings first, so the row is always the shorter one.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Compare the last letters: a match is used; otherwise drop one and recurse	O(2^(N + M))	O(N + M)
Better	dp[i][j] for every pair of prefixes; each cell is filled once from finished cells	O(N · M)	O(N · M)
Optimal	Keep only the row above and the current row; same rule, less memory	O(N · M)	O(min(N, M))

Why does this belong to this pattern?

Clues in the problem statement

“subsequence (letters can be skipped, order kept)”Gaps are allowed, so the answer is not a run of neighbours. That makes it LCS, not a substring.
“common to both strings”Two strings and one answer: compare prefixes of both at once with a table dp[i][j].
“return the length”We need a count, not the letters, so each cell stores one number.

Two strings+match → diagonal + 1+no match → max of the two skips→DP — Strings (LCS: match → diagonal + 1, else max of the two skips)

This question is the anchor of the sub-pattern. The rule is match → 1 + dp[i−1][j−1], and otherwise max(dp[i−1][j], dp[i][j−1]). The later questions in this sub-pattern reuse this table and change one thing. Watch the gap: a subsequence can skip letters, so a mismatch never resets the count to 0, unlike a substring.

Don't make this mistake

Pattern confusion: the common substring rule

✗ if (text1[i-1] == text2[j-1]) cur[j] = prev[j-1] + 1; else cur[j] = 0; // reset: a substring must be one unbroken run

✓ if (text1[i-1] == text2[j-1]) cur[j] = prev[j-1] + 1; else cur[j] = max(prev[j], cur[j-1]);

The substring rule resets to 0 on a mismatch, because a substring must be one unbroken run. A subsequence can skip letters. On the dry run (abcde and ace), the wrong rule returns 1, but the answer is 3. The letters a, c and e are never next to each other in abcde, so the run resets every time.

One row, updated left to right

✗ for (int j = 1; j <= m; j++) row[j] = (x == text2[j-1]) ? row[j-1] + 1 : max(row[j], row[j-1]);

✓ cur[j] = (x == text2[j-1]) ? prev[j-1] + 1 : max(prev[j], cur[j-1]); // prev = the old row

In the wrong version, row[j−1] has already been overwritten with this letter's value, so one letter of text1 can be used twice. With text1 = "a" and text2 = "aa", it returns 2, but the answer is 1, because text1 has only one a. Keep the old row in prev and write into cur.

Taking only the diagonal on a mismatch

✗ else cur[j] = prev[j-1]; // only the diagonal

✓ else cur[j] = max(prev[j], cur[j-1]);

When the letters differ, the answer can come from the cell above or the cell to the left, not just the diagonal. On the dry run, using only the diagonal on a mismatch returns 1, but the answer is 3.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture