Skip to main content

Longest Common Substring

Learn Longest Common Substring (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

The One Key Difference from LCS Longest Common Substring requires CONTIGUOUS matching characters. The DP recurrence is almost identical to LCS, but on a mismatch, dp[i][j] RESETS to 0 (instead of taking the max of neighbors) - a broken match must start completely over, since a substring can't have gaps.

More lessons in Dynamic Programming