Longest Common Substring Solution | Dataford Interview Questions

The City of Englewood Colorado may compare contiguous text segments from two records, such as matching portions of service descriptions. Given two strings, find their longest common substring, where matching characters must occur consecutively in both strings.

Return the substring itself. If multiple longest common substrings have the same length, return the one whose occurrence ends earliest in s1; if still tied, choose the one whose occurrence ends earliest in s2.

Formal Specification

Implement longest_common_substring(s1, s2), where s1 and s2 are strings. Return a string containing the longest contiguous sequence appearing in both inputs. Return "" when either input is empty or no characters match.

Use dynamic programming with rolling rows so the solution does not require a full two-dimensional table.

Constraints

0 <= len(s1), len(s2) <= 5,000
Inputs contain standard Python string characters
The result must be contiguous in both input strings
If multiple results tie, choose the one ending earliest in s1, then earliest in s2
Target complexity is O(len(s1) * len(s2)) time and O(len(s2)) auxiliary space

Function Signature

def longest_common_substring(s1, s2):

Your question is Longest Common Substring Solution. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem