207. Longest Common Substring

Given two strings, find the length of their longest common substring - a contiguous run of characters (not just any subsequence) that appears in both.

Input: The input consists of two lines, each containing one string (s1 and s2). Output: Print a single integer - the length of the longest common substring.

1 <= |s1|, |s2| <= 2000

Confusing 'longest common subsequence' (characters in order, gaps allowed) with 'longest common substring' (must be contiguous) is one of the most common mix-ups in string DP - always double-check which one a problem is actually asking for.

Find the length of the longest CONTIGUOUS run of characters common to two strings. Brute force: Check every possible pair of starting positions (one in each string) and extend a match as far as possible from each - this costs O(|s1| * |s2| * min length), when the DP table computes all such extensions simultaneously in one pass. Optimised: The DP directly captures 'the run ending HERE' for every position pair, resetting to 0 on any mismatch - since a substring must be CONTIGUOUS, there's no benefit to carrying over a previous best (unlike LCS, where skipping a character is always an option); tracking the MAXIMUM dp value seen anywhere gives the true longest common substring length.

For every pair of starting indices i in s1 and j in s2, walk forward comparing characters as long as they match, tracking the longest run found. This directly implements the definition of a common substring (a contiguous match) and is guaranteed correct, but it repeats the same comparisons over and over since overlapping runs starting at nearby indices share most of their characters. Time: O(n * m * min(n, m)) Space: O(1)

Build a table dp[i][j] representing the length of the common substring ending exactly at s1[i-1] and s2[j-1]. If the characters match, dp[i][j] = dp[i-1][j-1] + 1 (extending the previous match by one character); otherwise dp[i][j] = 0 (a common substring must be contiguous, so a mismatch resets it). The answer is the maximum value anywhere in the table. This reuses previously computed match lengths instead of re-walking from scratch, cutting the cost down to one multiplication of the two lengths. Time: O(n*m) Space: O(n*m)

Since dp[i][j] only ever depends on the previous row (dp[i-1][*]), the full 2D table can be replaced with two 1D rows (or a single row updated carefully) that get reused as the algorithm scans through s1. This keeps the same O(n*m) time but shrinks the memory footprint from the size of both strings multiplied together down to the size of just the shorter one, which matters once both strings approach the 2000-character upper bound. Time: O(n*m) Space: O(min(n, m))

1. dp[i][j] = length of the common substring ENDING exactly at s1[i-1] and s2[j-1]. 2. If s1[i-1]==s2[j-1], dp[i][j]=dp[i-1][j-1]+1. 3. Otherwise, dp[i][j]=0 (UNLIKE LCS, a mismatch RESETS the run to zero rather than carrying over the best-so-far).

Time: O(|s1| * |s2|) - filling the DP table, one cell per pair of positions. Space: O(|s1| * |s2|) for the full table (reducible to O(min(|s1|,|s2|)) with a rolling array).

Test strings with no characters in common (answer 0), strings that are identical, and both strings near the maximum length 2000 to confirm the O(|s1|*|s2|) DP runs in time.

Be ready to state the SINGLE crucial difference from LCS explicitly: LCS carries forward the best value on a mismatch (max of skipping either string's last character), while longest common SUBSTRING resets to 0 - this one-word difference in the recurrence is the entire distinction between the two problems.