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

Try every pair of start positions and extend the run while the letters match with time complexity O(N · M · min(N, M)) and space complexity O(1).

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

Keep one row; on a match row[j] = row[j − 1] + 1, on a mismatch 0; read j from high to low with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Longest Common Substring?

Look for key signals in the prompt: "substring" indicates A run of letters that sit next to each other. A gap means the run starts again from 0.; "appears in both strings" indicates The run must match in s1 and in s2 at the same time, so we compare pairs of positions, one from each string.; "longest length" indicates The answer is the largest run that ends at any pair, not the value at the last pair..

Longest Common Substring

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelDP — Strings, Common substring (run = diagonal + 1, reset on mismatch)

Complexity:O(N · M · min(N, M))→O(N · M)

Key Insight

The table only reads the row above it, so one row is enough. Overwrite that row in place. Go j from high to low, so that row[j − 1] still holds the row above when we read it. On a match, row[j] = row[j − 1] + 1. On a mismatch, row[j] = 0. The answer is the largest value ever written.

Core Validity Invariant

A common run must be contiguous, so on a mismatch the run restarts at 0. Then dp[i][j] is the length of the run that ends exactly at these two letters.

Problem

You get two strings, s1 and s2. Find the length of the longest substring that appears in both strings.

A substring is a run of characters that sit next to each other. A gap is not allowed. Matching is case-sensitive, so Y and y are different letters.

Return the length as a number.

Input

Two strings s1 and s2.

Output

A single number: the length of the longest common substring. It is 0 when the two strings share no letter.

Example 1

Input: s1 = "ABCDGH", s2 = "ACDGHR"

Output: 4

The longest common substring is "CDGH", which has length 4.

Example 2

Input: s1 = "abc", s2 = "acb"

Output: 1

Only single letters are shared as a run: "a", "b" and "c" each have length 1. The pair "ab" is in s1, but it is not a run in s2.

Example 3

Input: s1 = "YZ", s2 = "yz"

Output: 0

Matching is case-sensitive: Y is not y and Z is not z, so nothing is shared.

Constraints

• 1 ≤ s1.length, s2.length ≤ 10^3
• s1 and s2 contain only English letters.
• Matching is case-sensitive.

First, think yourself

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

1.
A subsequence can skip letters, but a substring cannot. Which one does this problem ask for?
2.
If the last letters of two prefixes match, how long is the common run that ends there?
3.
What should happen to the run when two letters differ? Can the run jump over that gap?
4.
Can the longest run end at any pair of positions, or only at the very end of both strings?
5.
Do I need the whole table, or only the row just above the one I am filling?

Brute force approach

Idea

Pick a start in s1 and a start in s2. Walk both forward together while the letters match, and record how far they go. Do this for every pair of starts and keep the longest run. Each walk starts from scratch, so the same letters are compared again and again.

Thinking process

1
Take s1 = ABCDGH and s2 = ACDGHR. Start at s1[0] = A and s2[0] = A. They match. Next, B and C do not match, so the run is 1.
2
Start at s1[2] = C and s2[1] = C. Then C, D, G, H all match, and s1 ends after H. The run is 4: CDGH.
3
Start at s1[3] = D and s2[2] = D. Then G = G and H = H, and s1 ends. The run is 3, but it is already part of the run CDGH from the step before.
4
Every pair of starts gives one run length. The biggest is 4, so the answer is 4.

Visual

Rows = s1 (ABAB), columns = s2 (BABA). Each cell is one pair of characters: = means they match, ≠ means they differ. Blue = a comparison in this run. Orange = a comparison an earlier start already made (the same diagonal is walked again). Red = the mismatch that ends a run. Purple = the best run so far.

Brute force: every start pairs1 = "ABAB", s2 = "BABA"step 1/18

≠

State

start pairs: 16
best run: 0

Start: try every pair of start positions (i, j)

The brute force starts a run at every pair (i, j). From each start it compares s1[i + t] with s2[j + t] while they match. Each cell of the grid is one pair of characters, marked = or ≠.

Code & Implementation

brute.cpp

class Solution {
public:
    int longCommSubstr(string& s1, string& s2) {
        int n = s1.size(), m = s2.size(), best = 0;
        // Every pair of start positions: extend the run while the characters match.
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int len = 0;
                while (i + len < n && j + len < m && s1[i + len] == s2[j + len]) len++;
                best = max(best, len);
            }
        return best;
    }
};

Complexity

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

N is the length of s1 and M the length of s2. There are N · M pairs of starts. From each one the walk goes at most min(N, M) steps, so the work is at most N · M · min(N, M) comparisons. With N = M = 1000 that is far too slow. The walks also repeat each other along the same diagonal of the table.

Better approach

Why brute force is slow

The brute force finds each run from scratch. The run DGH is found again inside the run CDGH, and it is compared letter by letter once more.

What repeated work are we doing?

A common run of length L is re-checked from each of its L starting points. The letters along each diagonal are compared again and again.

What information can we reuse?

dp[i][j] = dp[i − 1][j − 1] + 1 on a match. The run ending here is one longer than the run that ends at the previous diagonal pair. Each pair is computed once, and the table keeps every run.

New approach

Idea

Let dp[i][j] be the length of the common run that ends at s1[i − 1] and s2[j − 1]. On a match, dp[i][j] = dp[i − 1][j − 1] + 1: the run is the one ending one step earlier, plus this pair. On a mismatch, dp[i][j] = 0. The answer is the largest value in the table.

Thinking process

1
Take s1 = ABCDGH and s2 = ACDGHR. The pair s1[2] = C and s2[1] = C matches. That pair is cell dp[3][2]. Its diagonal cell dp[2][1] is 0, so dp[3][2] = 0 + 1 = 1.
2
Next, s1[3] = D and s2[2] = D match. That cell is dp[4][3], and its diagonal dp[3][2] is 1. So dp[4][3] = 2. The run CD is built from the run C.
3
Then dp[5][4] = 3 (CDG) and dp[6][5] = 4 (CDGH).
4
A mismatch resets the value: s1[1] = B and s2[5] = R differ, so dp[2][6] = 0.

Code & Implementation

better.cpp

class Solution {
public:
    int longCommSubstr(string& s1, string& s2) {
        int n = s1.size(), m = s2.size();
        // dp[i][j] = length of the common run that ends at s1[i-1] and s2[j-1].
        // Row 0 and column 0 are the empty prefix, so they stay 0.
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int best = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                // On a match, the run before this pair is the diagonal cell: add this pair to it.
                // On a mismatch dp[i][j] stays 0, because a substring must be contiguous.
                if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                best = max(best, dp[i][j]);
            }
        return best;
    }
};

Complexity

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

N is the length of s1 and M the length of s2. One cell per pair of positions, each with O(1) work. The table holds (N + 1) · (M + 1) integers. The optimal approach below keeps only the row it is filling.

Optimized approach

Idea

Start from brute force

The brute force starts a run from each pair and throws the work away. A run is just the run one diagonal step earlier, plus this pair, so the table reuses that run instead of rebuilding it.

Find the repeated work

A run of length L is re-checked from each of its L starting points, and the diagonal cells near its end are compared again and again.

Define the state — what variables do I need?

dp[i][j]: The length of the common run that ends at s1[i − 1] and s2[j − 1]. It is 0 when those two letters differ.
row[j]: dp[i][j] for the current i. It is one array, overwritten in place as i moves forward.
best: The largest dp value seen so far.

Define validity

A common run must be contiguous, so on a mismatch the run restarts at 0. Then dp[i][j] is the length of the run that ends exactly at these two letters.

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

s1[i − 1] = s2[j − 1]

row[j] = row[j − 1] + 1

The run that ends at the pair before them is dp[i − 1][j − 1], which row[j − 1] holds. This pair extends it by one letter.

s1[i − 1] ≠ s2[j − 1]

row[j] = 0

No common run can end at these two letters, and a substring cannot skip over the mismatch.

j goes from m down to 1

Read row[j − 1] before it is overwritten for this i

Going high to low means row[j − 1] has not changed yet for this i, so it still holds dp[i − 1][j − 1].

After each write

best = max(best, row[j])

A run can end at any pair, so the answer is the largest value anywhere in the table.

What does the current window add to the answer?

Each pair either extends the run before it or resets to 0. best keeps the longest run seen so far.

Code & Implementation

optimal.cpp

class Solution {
public:
    int longCommSubstr(string& s1, string& s2) {
        int n = s1.size(), m = s2.size();
        // row[j] = length of the common run ending at s1[i-1] and s2[j-1], for the current i.
        // Only the previous row is needed, so one row is overwritten in place.
        vector<int> row(m + 1, 0);
        int best = 0;
        for (int i = 1; i <= n; i++)
            // j goes high → low: row[j - 1] must still hold the previous row's value when we read it.
            for (int j = m; j >= 1; j--) {
                if (s1[i - 1] == s2[j - 1]) row[j] = row[j - 1] + 1;
                else row[j] = 0;                  // mismatch: the run restarts
                best = max(best, row[j]);         // the answer is the best run anywhere, not the last cell
            }
        return best;
    }
};

Complexity

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

N is the length of s1 and M the length of s2. Every pair of positions is visited once, with O(1) work each. The code keeps one row of M + 1 integers and the best value. A faster idea, binary search on the length with rolling hashes, runs in O((N + M) log N), but the DP is simpler and fast enough here.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try every pair of start positions and extend the run while the letters match	O(N · M · min(N, M))	O(1)
Better	Fill an (N + 1) × (M + 1) table; a match extends the diagonal cell by one	O(N · M)	O(N · M)
Optimal	Keep one row; on a match row[j] = row[j − 1] + 1, on a mismatch 0; read j from high to low	O(N · M)	O(M)

Why does this belong to this pattern?

Clues in the problem statement

“substring”A run of letters that sit next to each other. A gap means the run starts again from 0.
“appears in both strings”The run must match in s1 and in s2 at the same time, so we compare pairs of positions, one from each string.
“longest length”The answer is the largest run that ends at any pair, not the value at the last pair.

Two sequences+Match extends the diagonal+Mismatch resets to 0+Maximum over all cells→DP — Strings, Common substring (run = diagonal + 1, reset on mismatch)

This is the anchor of the Common substring family. The rule that changes everything is the reset: on a mismatch the run goes to 0, not to the best value of the cell above or to the left. That reset is what separates it from the subsequence problem, LCS, which carries the best value across a gap. Maximum Length of Repeated Subarray applies the same rule to integer arrays.

Don't make this mistake

Pattern confusion: using the LCS rule on a mismatch

✗ dp[i][j] = s1[i-1] == s2[j-1] ? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);

✓ dp[i][j] = s1[i-1] == s2[j-1] ? dp[i-1][j-1] + 1 : 0;

The max rule computes the longest common subsequence, which may skip letters. On the dry run (ABCDGH and ACDGHR) this rule gives 5, the length of the subsequence ACDGH with gaps. The longest common substring is 4 (CDGH), because a substring cannot skip a letter.

Returning the last cell instead of the best cell

✗ return dp[n][m];

✓ return best;

The longest run can end anywhere. On ABCDGH and ACDGHR the last pair is H and R, which differ, so dp[6][6] = 0. The wrong code returns 0 instead of 4.

Going low to high in the one-row version

✗ for (int j = 1; j <= m; j++) { if (s1[i-1] == s2[j-1]) row[j] = row[j-1] + 1; else row[j] = 0; }

✓ for (int j = m; j >= 1; j--) { ... }

Going low to high, row[j − 1] has already been overwritten with this row's value, so the run grows through the wrong letters. On the dry run the answer becomes 1 instead of 4.

Want to implement this?

Write it yourself on GeeksforGeeks, 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