DSA AnimatorDSA animations
Longest Common Substring GFG Medium 2D DP
Problem

Given two strings, find the length of their longest common substring (contiguous sequence). Unlike subsequence, substring must be contiguous — mismatch resets to 0.

Example 1
Input: "abcdxyz", "xyzabcd"
Output: 4
Match: dp[i][j]=dp[i-1][j-1]+1. Mismatch: dp[i][j]=0. Track max.
Try Examples
Custom:
Approach
2D DP — match → dp[i-1][j-1]+1, else 0
dp[i][j] = longest common suffix ending at s[i-1], t[j-1]. Mismatch breaks streak → 0. Track max.
DP Table
Load an example to begin.
Variables
i, j
—
match?
—
dp[i][j]
—
ans
—
Step Logic
Press ▶ Play or Next Step to begin.
📏
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[i][j] = longest common suffix ending at s[i-1], t[j-1]
2
Match → dp[i][j] = dp[i-1][j-1] + 1 (extend diagonal)
3
Mismatch → dp[i][j] = 0 (streak broken)
4
ans = max over all dp[i][j]
Time
O(m×n)
Space
O(m×n)
Why This Works

Unlike subsequence, substring is contiguous. Any mismatch resets the cell to 0. Match extends the diagonal streak. Answer = peak value in table; trace back diagonally for actual substring.

How to solve Longest Common Substring

GFG · Medium · Dynamic Programming · Pattern: 2D String DP

Why the obvious approach is slow

Checking every substring of one string against the other is O(n) cubed or worse. Prefix tables again give a quadratic solution.

The key idea

Let dp of i and j be the length of the common substring that ends exactly at character i of the first string and character j of the second. If the characters match, extend the diagonal: dp of i −1, j −1, plus 1. If they do not match, the run is broken, so the value is 0. That reset to 0 is the only difference from the subsequence version. The answer is the largest value anywhere in the table, not the bottom right cell.

Remember

A mismatch resets a substring to 0. The answer is the maximum cell, wherever it is.

Run the animation above on your own input, or watch the 1:48 video explanation of Longest Common Substring with a dry run and Java code.

More Dynamic Programming problems