Longest Common Substring — DP, Rolling Hash, and Suffix Array Approaches

Problem Statement#

Given two strings s1 and s2, find the longest substring that appears as a contiguous substring in both. Return either the substring itself or its length, depending on the variant.

Important distinction: "Substring" means a contiguous slice. "Subsequence" means characters in order but not necessarily contiguous. The longest common subsequence (LCS) and longest common substring are different problems with different DP recurrences.

Examples:

• s1 = "ABABC", s2 = "BABCA" -> longest common substring is "BABC" (length 4).
• s1 = "abcdef", s2 = "zcdey" -> longest common substring is "cde" (length 3).

Constraints (typical): 1 <= n, m <= 10^4 for DP, up to 10^6 for hashing or suffix array.

Why This Problem Matters#

Longest common substring is a foundational problem with applications across bioinformatics (sequence alignment), version control (diff and merge), plagiarism detection (MOSS, JPlag), and search engines (relevance scoring). Solving it well requires touching three of the major string-algorithms toolkits — dynamic programming, rolling hash, and suffix arrays — making it a perfect interview prompt for senior candidates.

Google, Meta, and Amazon all use this problem as a "what is your toolkit" probe. The DP solution is table stakes; mentioning binary search plus rolling hash earns medium signal; sketching the suffix array approach earns strong signal. The problem also sets up follow-ups about k-mismatches, multiple strings, and online queries.

In production, the DP version powers Unix diff (a generalisation tracks insertions and deletions). The hash version is the basis of MinHash and other locality-sensitive hashing techniques. The suffix-array version underpins the Smith-Waterman alignment used in BLAST.

Strategically, this problem is a great vehicle to show off your full string-algorithms repertoire in one breath. State all three approaches, justify the choice based on input size, then implement the most appropriate one.

The Core Insight#

The DP recurrence is short. Define dp[i][j] as the length of the longest common substring ending at s1[i-1] and s2[j-1]. Then:

dp[i][j] = dp[i-1][j-1] + 1   if s1[i-1] == s2[j-1]
         = 0                    otherwise

The answer is max(dp[i][j]) across all i, j. The tricky part is "ending at" — this is what makes it different from longest common subsequence, where mismatches don't reset the chain.

Space optimisation: only the previous row is needed, so we can use two 1D arrays of length m+1.

The DP is O(n*m) time, prohibitive when n and m reach 10^6.

Hash-based binary search. Observe that if a common substring of length L exists, then so do all common substrings of length less than L. Binary search on L. For each candidate L, compute hashes of all length-L substrings of s1 and store them in a set, then check whether any length-L substring of s2 has a hash in the set. Total time: O((n + m) log min(n, m)).

Suffix array. Concatenate s1 + '#' + s2 + '$', build the suffix array and LCP. Adjacent suffixes in the SA with one originating from s1 and the other from s2 correspond to candidate common substrings; the LCP between them is the length of that common substring. Take the maximum across qualifying pairs. Total time: O((n + m) log(n + m)) for suffix array construction.

Each approach has its niche. DP is simplest and has the cleanest implementation. Hashing scales to large inputs but requires careful collision handling. Suffix array is deterministic but has the highest constant factor.

Visual Dry Run#

s1 = "ABCBDAB", s2 = "BDCABA". Build the DP table:

      ''  B  D  C  A  B  A
  ''   0  0  0  0  0  0  0
   A   0  0  0  0  1  0  1
   B   0  1  0  0  0  2  0
   C   0  0  0  1  0  0  0
   B   0  1  0  0  0  1  0
   D   0  0  2  0  0  0  0
   A   0  0  0  0  1  0  1
   B   0  1  0  0  0  2  0

The maximum value is 2, occurring at multiple cells. The longest common substring is one of "AB", "BD", or "BA" (all length 2).

For a longer example, s1 = "ABABC", s2 = "BABCA":

      ''  B  A  B  C  A
  ''   0  0  0  0  0  0
   A   0  0  1  0  0  1
   B   0  1  0  2  0  0
   A   0  0  2  0  0  1
   B   0  1  0  3  0  0
   C   0  0  0  0  4  0

Maximum is 4 at dp[5][4]. The substring is s1[5-4..4] = s1[1..4] = "BABC". Length 4.

The "trail of increasing diagonals" is the visual signature: every diagonal of consecutive matches is a common substring, and DP records its length at the bottom-right cell.

Solution (Optimal)#

Python — DP with Space Optimisation#

def longest_common_substring(s1: str, s2: str) -> str:
    m, n = len(s1), len(s2)
    if m == 0 or n == 0:
        return ""
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    best_len = 0
    best_end = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
                if curr[j] > best_len:
                    best_len = curr[j]
                    best_end = i
            else:
                curr[j] = 0
        prev, curr = curr, [0] * (n + 1)
    return s1[best_end - best_len:best_end]
 
 
def longest_common_substring_hash(s1: str, s2: str) -> int:
    """Binary search + rolling hash, returns length only."""
    MOD = (1 << 61) - 1
    BASE = 131
 
    def get_hashes(s, length):
        if length > len(s):
            return set()
        h = 0
        power = pow(BASE, length, MOD)
        # initial window
        for c in s[:length]:
            h = (h * BASE + ord(c)) % MOD
        out = {h}
        for i in range(length, len(s)):
            h = (h * BASE + ord(s[i]) - ord(s[i - length]) * power) % MOD
            out.add(h)
        return out
 
    lo, hi = 0, min(len(s1), len(s2))
    best = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid == 0:
            best = 0
            lo = mid + 1
            continue
        if get_hashes(s1, mid) & get_hashes(s2, mid):
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return best

JavaScript — DP with Space Optimisation#

function longestCommonSubstring(s1, s2) {
  const m = s1.length, n = s2.length;
  if (m === 0 || n === 0) return "";
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);
  let bestLen = 0, bestEnd = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
        if (curr[j] > bestLen) {
          bestLen = curr[j];
          bestEnd = i;
        }
      } else {
        curr[j] = 0;
      }
    }
    [prev, curr] = [curr, new Array(n + 1).fill(0)];
  }
  return s1.slice(bestEnd - bestLen, bestEnd);
}

Complexity:

• DP: O(n*m) time, O(min(n, m)) space with rolling rows.
• Hash + binary search: O((n + m) log min(n, m)) expected.
• Suffix array: O((n + m) log(n + m)) construction plus O(n + m) scan.

Common Mistakes#

Confusing substring with subsequence. Subsequence allows skipping characters; substring does not. The DP recurrences differ at the mismatch case: subsequence takes max(dp[i-1][j], dp[i][j-1]), substring resets to 0.

Forgetting to reset on mismatch. Easy to type dp[i][j] = dp[i-1][j-1] for both branches. The reset to 0 is what enforces contiguity.

Tracking "best end" instead of "best start" in the rolling row case. When you collapse to two rows, you lose the diagonal trace. Track best_end (or equivalently best_i) at the moment you update the maximum, then slice s1[best_end - best_len:best_end].

Hash collisions in the binary search version. Without verification, two different length-L substrings can hash to the same value and produce a false positive. Use double hashing or store actual substrings keyed by hash and verify on collision.

Wrong comparator in suffix array variant. When concatenating s1 + '#' + s2, you must ensure the LCP between adjacent suffixes does not span the # separator — i.e., LCP is bounded by the distance to the nearest # in the suffix. Otherwise you report an "L" that includes the separator.

Memory overflow on large inputs. Full O(n*m) table at n = m = 10000 is 10^8 cells — borderline 400 MB at 32-bit. Always optimise to two rolling rows, or use hashing if the input is larger.

Interview Tips#

State the recurrence and the substring/subsequence distinction explicitly. Many candidates conflate the two; clarifying upfront earns credit.

Walk through a small DP table on the whiteboard before coding. The visual diagonals make the recurrence intuitive and catch interviewer questions early.

After the DP version works, mention the binary search plus rolling hash approach for larger inputs. Even without coding it, articulating the O((n + m) log min(n, m)) bound and the collision concern shows depth.

For very large inputs (n = m = 10^6), the suffix array approach is canonical. Sketch the concatenation with sentinel and LCP scan; emphasise that the constraint "different sides of the sentinel" is what makes adjacent-LCP analysis correct.

If asked about k-mismatches (longest common substring allowing up to k differences), shift to suffix automata or specialised algorithms. Hashing extends with polynomial composition tricks but DP becomes O(nmk).

For the multi-string version (longest common substring of more than two strings), generalise the suffix array approach: concatenate all with distinct sentinels, then use a sliding window over the SA that contains at least one suffix from each input.

Follow-up Questions#

Q: How do you find all longest common substrings, not just one? A: During the DP, maintain a list of (i, j) positions where dp[i][j] == best_len. After the table is built, extract substrings ending at each position. Deduplicate if needed.

Q: What is the complexity of Smith-Waterman alignment? A: O(n*m) like our DP, but it allows insertions, deletions, and substitutions weighted by a scoring matrix. The longest-common-substring problem is the special case where only matches contribute.

Q: How do you extend to the longest common substring of k strings? A: Concatenate with k distinct sentinels and build a suffix array. Use a sliding window over consecutive suffixes that touches all k strings; the minimum LCP within each window is a candidate. Total time O(N log N) where N is the sum of lengths.

Q: Can you do this online, where strings arrive incrementally? A: Yes — using a suffix automaton or generalised suffix tree. Both support online insertions and answer "longest common substring with all known strings" in O(1) amortised per new character.

Q: Why does hashing give expected linear behaviour on this problem? A: Each binary search step is O(n + m). There are O(log min(n, m)) steps. So total expected work is O((n + m) log min(n, m)). In practice, hashing is faster than DP for n + m above a few thousand because of cache-friendly linear scans.

Key Takeaways#

• Longest common substring requires substring (contiguous), not subsequence; the DP recurrence resets to zero on mismatch instead of taking a max from neighbours.
• DP solves the problem in O(n*m) with O(min(n, m)) rolling-row space; track best_end and best_len to recover the actual substring.
• Binary search plus rolling hash gives O((n + m) log min(n, m)) expected and scales to inputs of size 10^6 and beyond, but requires collision-safe hashing.
• Suffix array plus LCP, after concatenation with a sentinel, gives a deterministic O((n + m) log(n + m)) solution with the cleanest theoretical bound.
• The choice of approach depends on input size, presence of mismatches, and online vs offline access patterns.
• Interview signal: knowing all three approaches and choosing wisely demonstrates the full string-algorithms toolkit FAANG seniors are expected to have.