Longest Common Substring

Given two strings s1 and s2, return the length of the longest substring that appears in both strings. Unlike subsequences, substrings must be contiguous. Pattern focus: LCS Style DP. This is the classic diagonal-transition string DP with zero reset on mismatch.

Input Format

s1 = first string, s2 = second string

Output Format

length of the longest common substring

Constraints

  • 0 <= s1.length, s2.length <= 1000
  • s1 and s2 contain lowercase English letters.

Examples

Example 1:

Input:

s1 = "abcdxyz"
s2 = "xyzabcd"

Output:

4

Explanation:

The longest common substring is abcd or xyz.

Example 2:

Input:

s1 = "abc"
s2 = "bcd"

Output:

2

Explanation:

The longest common substring is bc.

Loading...
Longest Common Substring - Dp Strings