Longest common substring

Hard

Reset to zero on a mismatch

Problem

Return the length of the longest common substring (contiguous) of two strings.

In simple words

Grow a matching run on the diagonal; a mismatch resets it to 0, and you track the longest.

The idea

Unlike a subsequence, a substring must be contiguous, so a mismatch destroys the run: dp[i][j] is 1 + the diagonal when the characters match and 0 otherwise. The answer is the largest value anywhere in the table, not the last cell.

The trick

Mismatch means 0, not a carry-over from the neighbours.
Track the maximum as you fill; the final cell is not the answer.

←→stepspaceplay

∅

1/8

Optimal

timeO(n·m)spaceO(n·m)

Match extends the diagonal.

1for (let i = 1; i <= n; i++)2  for (let j = 1; j <= m; j++)3    dp[i][j] = a[i-1] === b[j-1]4      ? dp[i-1][j-1] + 15      : Math.max(dp[i-1][j], dp[i][j-1]);

Input

grid: 5 × 4

Memory

at: —
cells marked: 0

Output

LCS: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: a = "abcde", b = "abfce"
Output:: 2
Explanation:: The shared run "ab" has length 2.

Example 2

Input:: a = "abcdxyz", b = "xyzabcd"
Output:: 4
Explanation:: "abcd" matches → length 4.

Example 3

Input:: a = "abc", b = "def"
Output:: 0
Explanation:: Nothing shared → 0.

Practice this problem:LeetCode(opens in a new tab)GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.