Dynamic Programming • 2D Arrays

Longest Common Substring

Find the length of the longest contiguous sequence of characters that appear in both strings. A stricter variation of LCS.

Try Interactive Simulator

Overview

Unlike Longest Common Subsequence, a Substring must be contiguous. This means the moment two characters don't match, the streak is broken.

The State

`dp[i][j]` represents the length of the longest common substring ENDING at `s1[i-1]` and `s2[j-1]`.

The Reset

If characters match, `dp[i][j] = 1 + dp[i-1][j-1]`. If they do NOT match, `dp[i][j] = 0`. We don't carry over the max from Top or Left like in LCS.

Global Max

Because the longest substring could end anywhere in the strings, the final answer isn't necessarily `dp[m][n]`. We track `maxLen` dynamically during the loop.

S1 \ S2	""	a	b	z	d	f
""	0	0	0	0	0	0
a	0	0	0	0	0	0
b	0	0	0	0	0	0
c	0	0	0	0	0	0
d	0	0	0	0	0	0
f	0	0	0	0	0	0

Code Tracker

:::

1let maxLen = 0;

2for (let i = 1; i <= m; i++) {

3 for (let j = 1; j <= n; j++) {

4 if (text1[i-1] === text2[j-1]) {

5 dp[i][j] = 1 + dp[i-1][j-1];

6 maxLen = Math.max(maxLen, dp[i][j]);

7 } else {

8 dp[i][j] = 0; // Contiguous rule

9 }

10 }

11}

12return maxLen;