← Back to DSA Animator
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.