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.