Longest Common Substring
Implement longestCommonSubstring
Given two strings
s1 and s2, find the length of their longest common substring — a run of characters that appears identically, and contiguously, in both strings.
This looks close to the longest common *subsequence* problem, but one rule flips the whole approach: a subsequence can skip characters, so its DP table only ever grows or copies forward from a neighbor; a substring can't skip anything, so the moment two characters fail to match, whatever run was building there is completely over — the table entry resets to 0 instead of falling back on a neighbor's value. Tracking, for every pair of positions, "how long is the run that ends exactly here" turns every comparison into a single lookup, and the answer is just the largest number that ever shows up anywhere in that table.
Example 1:
Input: s1 = "geeksforgeeks", s2 = "geeksquiz"
Output: 5
Example 2:
Input: s1 = "abc", s2 = "def"
Output: 0
Example 3:
Input: s1 = "", s2 = "abc"
Output: 0
+ 7 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ s1.length, s2.length ≤ 13 - ●
s1 and s2 consist of lowercase English letters only
s1 =
geeksforgeeks
s2 =
geeksquiz