PreviousNext
Coding/Dynamic programming

Longest common substring

Write codeMedium30 min

Your task

Return the length of the longest substring that appears contiguously in BOTH strings a and b (the longest common substring, not subsequence). For example "abcdxyz" and "xyzabcd" share "abcd" of length 4. Either string may be empty (answer 0). Strings can be up to ~1000 characters; an O(len(a)*len(b)) DP is acceptable, though suffix automata/arrays give better asymptotics.

Examples

longest_common_substring_len(a: str, b: str) -> int
Example 1
Inputlongest_common_substring_len("AcornforAcorn", "AcornQuiz")
Output5