Maximal Common Substring | Dataford Interview Questions

A TotalEnergies OneTech data pipeline compares operational identifiers from two systems. Given two strings, return their longest common contiguous substring.

Unlike a subsequence, every character in the result must occupy consecutive positions in both input strings. If multiple longest common substrings exist, return the one whose starting position is earliest in s1. If there is no common character, return an empty string.

Formal Specification

Implement longest_common_substring(s1, s2), where both inputs are strings. Return a string containing the longest substring that appears in both s1 and s2. Matching is case-sensitive, and characters include letters, digits, spaces, and punctuation.

Your solution should use dynamic programming and limit auxiliary space to O(min(len(s1), len(s2))).

Constraints

0 <= len(s1), len(s2) <= 5000
Inputs contain standard Unicode characters
Matching is case-sensitive
The result must be contiguous in both strings
For equal-length answers, return the one with the earliest start in s1

Function Signature

def longest_common_substring(s1, s2):

Your question is Maximal Common Substring. 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