Solving Longest Common Substring with Dynamic Programming

1. Introduction and Core Concepts

The longest common substring problem is a fundamental string processing challenge that asks a deceptively simple question: given two strings, what is the longest contiguous sequence of characters that appears in both? Unlike its close relative the longest common subsequence, where characters need not be adjacent, a substring must be strictly contiguous. For example, given the strings "ABABC" and "BABCA", the longest common substring is "BABC" with length 4, while "ABC" is also a common substring but not the longest. This distinction is critical because it fundamentally changes the underlying dynamic programming recurrence and the applications for which each problem is suitable.

Understanding the longest common substring is essential for any developer working with text processing, data comparison, or sequence analysis. The problem exhibits optimal substructure and overlapping subproblems, the two hallmark properties that make dynamic programming an ideal solution technique. When we compare prefixes of the two strings, the solution for longer prefixes can be built directly from solutions for shorter prefixes. This property allows us to avoid the exponential cost of naive brute-force enumeration, which would generate all substrings of both strings and compare them one by one. For strings of length m and n, a brute-force approach would consider O(m^2) substrings from the first string and O(n^2) from the second, leading to prohibitive runtime for even moderately sized inputs.

The importance of the longest common substring extends far beyond academic exercises. It forms the computational backbone for plagiarism detection systems, genome sequence alignment, diff utilities, spam filtering, and autocomplete engines. In bioinformatics, finding conserved regions between DNA sequences can reveal evolutionary relationships. In version control systems like Git, identifying common blocks between file versions enables efficient storage and merging. Mastering the dynamic programming solution not only provides an efficient O(m * n) algorithm but also builds intuition for a whole class of two-dimensional DP problems including edit distance, longest common subsequence, and regular expression matching.

Substring vs. Subsequence: A Critical Distinction

A common source of confusion for learners is the difference between substring and subsequence. A substring requires contiguity; you cannot skip characters. A subsequence allows gaps. For instance, for strings "ABCDE" and "ACE", the longest common subsequence is "ACE" (length 3), but the longest common substring is "A" or "C" or "E" (length 1), since no two consecutive characters match in order. This contiguity constraint simplifies the DP recurrence in one way but requires careful handling of mismatches. When characters do not match, the DP value resets to zero rather than carrying over a previous maximum, which is exactly the opposite of the subsequence recurrence.

This constraint also affects how we reconstruct the answer. For the longest common subsequence, we typically backtrack through the entire DP table to rebuild the sequence. For the longest common substring, we only need to track the maximum value encountered during table filling and its ending position. The substring itself can then be extracted directly via slicing. This makes implementation slightly simpler and more memory-friendly if we only need the length, though reconstructing all longest common substrings when there are multiple ties requires additional bookkeeping.

2. How It Works

The dynamic programming approach to the longest common substring builds a two-dimensional table dp where dp[i][j] represents the length of the longest common suffix of the prefixes s1[0:i] and s2[0:j]. More precisely, dp[i][j] is the length of the longest common substring ending exactly at s1[i-1] and s2[j-1]. This definition is crucial: it does not store the longest common substring found anywhere within those prefixes, but only those that end at the current characters. The global answer is the maximum value ever written into the table.

The recurrence relation follows directly from this definition. To compute dp[i][j], we compare the characters s1[i-1] and s2[j-1]. If they are equal, then any common suffix ending at these characters must extend the common suffix ending at the previous characters. Therefore, dp[i][j] = dp[i-1][j-1] + 1. If the characters are different, no common suffix can end at this position, so dp[i][j] = 0. This reset to zero is the defining characteristic that enforces contiguity. The base cases are dp[0][j] = 0 for all j and dp[i][0] = 0 for all i, representing that an empty prefix has no common substring with any string.

As we fill the table row by row, typically from top-left to bottom-right, we maintain two auxiliary variables: max_length, which stores the largest value seen so far, and end_index, which stores the ending position in s1 where that maximum occurs. Whenever dp[i][j] exceeds max_length, we update both variables. At the end of the computation, the longest common substring can be recovered as s1[end_index - max_length : end_index]. This approach ensures we find the length and one instance of the longest common substring in a single pass without a separate backtracking phase, although backtracking can be used if we want to enumerate all maximal substrings.

The DP Table Intuition

Visually, the DP table can be thought of as an alignment grid between the two strings. Matches create diagonal chains of increasing numbers, while mismatches break those chains. The longest common substring corresponds to the longest diagonal of consecutive increments in the table. For example, if s1 = "ABABC" along the rows and s2 = "BABCA" along the columns, the diagonal corresponding to "BABC" will appear as the sequence 1, 2, 3, 4 along adjacent diagonal cells. This geometric interpretation is helpful for debugging and for understanding why the algorithm works. It also reveals why space optimization is possible: to compute the current row, we only need the previous row, not the entire history.

The optimal substructure property is evident here: the solution for dp[i][j] depends only on the solution for the strictly smaller subproblem dp[i-1][j-1] plus the decision about the current characters. There are no dependencies on dp[i-1][j] or dp[i][j-1] as in the longest common subsequence problem. This simpler dependency graph means fewer table lookups and a slightly tighter inner loop, though the asymptotic complexity remains quadratic. Understanding this dependency is key to implementing the space-optimized version correctly, where overwriting values in the wrong order can corrupt the needed diagonal predecessor.

3. Implementation

Implementing the longest common substring with dynamic programming in Python is straightforward and highly instructive. The classic implementation uses a full (m+1) x (n+1) table, which is easiest to understand and debug. While it uses O(m * n) space, it clearly demonstrates the recurrence and makes it easy to reconstruct the substring. For production code or large inputs, we will later optimize the space to O(min(m, n)). Below are several implementations progressing from clarity to efficiency, each with detailed comments and handling for edge cases such as empty strings and multiple equally-long answers.

The first implementation is the canonical DP solution. It initializes a table with zeros, iterates through both strings, applies the recurrence, and tracks the maximum. It returns both the substring and its length. Note how we handle Python's zero-based indexing by offsetting the DP table by one, so dp[i][j] corresponds to s1[i-1] and s2[j-1]. This avoids complex boundary checks inside the inner loop.

def longest_common_substring_basic(s1, s2):
    """
    Classic O(m*n) time and space DP for longest common substring.
    Returns one longest common substring and its length.
    """
    m, n = len(s1), len(s2)
    if m == 0 or n == 0:
        return "", 0

    # dp[i][j] = length of longest common suffix ending at s1[i-1] and s2[j-1]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end_pos = 0  # ending index in s1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0

    # Extract substring using end position and length
    lcs = s1[end_pos - max_len:end_pos]
    return lcs, max_len

While the basic version is clear, it allocates a full matrix which can be wasteful. If we only need the length of the longest common substring, we can reduce space to O(min(m, n)) by keeping only two rows: the previous row and the current row. The challenge is to correctly preserve the diagonal value dp[i-1][j-1] before it is overwritten. The following optimized version also ensures we iterate over the shorter string for the inner dimension to minimize memory.

def longest_common_substring_optimized(s1, s2):
    """
    Space-optimized DP: O(m*n) time, O(min(m,n)) space.
    Returns length and one longest substring.
    """
    # Ensure s2 is the shorter string to minimize space
    if len(s1) < len(s2):
        s1, s2 = s2, s1

    m, n = len(s1), len(s2)
    if n == 0:
        return "", 0

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    max_len = 0
    end_pos = 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] > max_len:
                    max_len = curr[j]
                    end_pos = i
            else:
                curr[j] = 0
        # Swap rows for next iteration
        prev, curr = curr, prev
        # Reset curr (which is now old prev) for reuse
        for k in range(n + 1):
            curr[k] = 0

    return s1[end_pos - max_len:end_pos], max_len

In many applications, there may be multiple distinct substrings that tie for the longest length. For example, "ABAB" and "BABA" have both "ABA" and "BAB" as longest common substrings of length 3. The next implementation collects all such substrings using a set to avoid duplicates. It still uses the full DP table for clarity, but tracks a set of results and updates it whenever a new maximum is found or another substring ties the current maximum.

def longest_common_substring_all(s1, s2):
    """
    Returns all distinct longest common substrings.
    Time O(m*n), Space O(m*n) for table + O(k*l) for results.
    """
    m, n = len(s1), len(s2)
    if m == 0 or n == 0:
        return set(), 0

    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    result_set = set()

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    result_set = {s1[i - max_len:i]}
                elif dp[i][j] == max_len and max_len > 0:
                    result_set.add(s1[i - max_len:i])
            else:
                dp[i][j] = 0

    return result_set, max_len

Finally, for completeness, here is a helper that reconstructs the DP table itself for visualization and debugging. This is invaluable when teaching the algorithm or when you need to inspect the table for step-by-step analysis. It returns the full matrix so you can print it or render it as a heatmap.

def build_lcs_table(s1, s2):
    """
    Build and return the full DP table for inspection.
    Useful for debugging and step-by-step walkthroughs.
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
    return dp

def print_table(s1, s2, dp):
    # Print header row
    header = "      " + "  ".join([" " + ch for ch in s2])
    print(header)
    for i in range(len(dp)):
        row_label = " " if i == 0 else s1[i - 1]
        row_vals = "  ".join(str(v) for v in dp[i])
        print(f"{row_label} | {row_vals}")

4. Step-by-Step Example

To solidify the mechanics, let us walk through a concrete example in detail. Consider s1 = "ABABC" and s2 = "BABCA". We will construct the DP table step by step. We create a table with dimensions (m+1) x (n+1) = 6 x 6, where the extra first row and column represent empty prefixes and are initialized to zero. The rows correspond to characters of s1 (with an initial empty row), and the columns correspond to characters of s2.

We begin filling row by row. For i=1 (s1[0] = 'A'), we compare 'A' against each character of s2 = "B A B C A". At j=1 ('B'), mismatch so dp[1][1]=0. At j=2 ('A'), match so dp[1][2]=dp[0][1]+1=1. At j=3 ('B'), mismatch so 0. At j=4 ('C'), 0. At j=5 ('A'), match so dp[1][5]=dp[0][4]+1=1. The maximum so far is 1. For i=2 (s1[1]='B'), we compare 'B' against s2. At j=1 ('B'), match so dp[2][1]=dp[1][0]+1=1. At j=2 ('A'), mismatch 0. At j=3 ('B'), match so dp[2][3]=dp[1][2]+1=2, which becomes the new maximum (length 2 corresponds to "AB"). At j=4 ('C'), 0. At j=5 ('A'), 0.

Continuing, i=3 (s1[2]='A'): j=1 'B' mismatch 0, j=2 'A' match dp[3][2]=dp[2][1]+1=2 (substring "BA"), j=3 'B' mismatch 0, j=4 'C' 0, j=5 'A' match dp[3][5]=dp[2][4]+1=1. i=4 (s1[3]='B'): j=1 'B' match 1, j=2 'A' 0, j=3 'B' match dp[4][3]=dp[3][2]+1=3 (substring "BAB"), j=4 'C' 0, j=5 'A' 0. i=5 (s1[4]='C'): j=1 'B' 0, j=2 'A' 0, j=3 'B' 0, j=4 'C' match dp[5][4]=dp[4][3]+1=4 (substring "BABC"), j=5 'A' 0. The maximum value in the entire table is 4, ending at s1[4] (0-indexed position 3, 1-indexed row 5). Extracting s1[5-4:5] = s1[1:5] = "BABC", which is indeed the longest common substring.

Visualizing the Completed Table

The completed DP table for this example looks as follows, with rows labeled by s1 and columns by s2. Notice the diagonal chain 1→2→3→4 that forms the answer. Every time characters match, the value increments diagonally; every mismatch resets to zero, breaking any chain. This visualization makes it easy to spot all common substrings, not just the longest, by looking for any non-zero entries.

When tracing back from the maximum cell dp[5][4]=4, we can follow the diagonal backwards: dp[5][4] came from dp[4][3]=3, which came from dp[3][2]=2, which came from dp[2][1]=1. This path corresponds exactly to aligning "BABC" from both strings. If we wanted to find all longest substrings, we would scan the entire table for any other cells also containing the value 4, though in this example there is only one. This walkthrough demonstrates why tracking max_len and end_pos during the fill is sufficient and why no separate backtracking pass is needed if you only need one answer.

5. Complexity Analysis

Complexity analysis is crucial for deciding when the dynamic programming solution is appropriate and when alternative algorithms should be considered. The longest common substring DP has predictable performance characteristics that depend primarily on the lengths of the two input strings, denoted m and n. Unlike some algorithms where best-case and worst-case differ dramatically due to early termination, the standard DP fills the entire table regardless of input content, leading to consistent runtime. However, space usage and minor optimizations can introduce variations.

Time complexity is dominated by the nested loops that visit each cell of the DP table exactly once. Each cell computation is O(1), involving a character comparison and at most one integer addition. Therefore, total time is proportional to the number of cells, which is (m+1)*(n+1), or O(m * n). This holds for best, average, and worst cases because the algorithm does not have a mechanism to skip cells; even if the strings share no characters, every cell must still be examined to confirm the mismatch. The only way to achieve sub-quadratic time is to use a fundamentally different approach such as suffix trees or binary search with hashing.

Space complexity depends on the implementation variant. The naive full-table version stores the entire (m+1) x (n+1) integer matrix, requiring O(m * n) space. The optimized two-row version reduces this to O(min(m, n)) by keeping only the previous and current rows, which is a significant saving for long strings. If we also need to reconstruct all longest substrings or provide the full table for debugging, we must retain the full matrix. An even more space-efficient variant can use a single row plus a variable to store the diagonal predecessor, achieving O(min(m, n)) with a smaller constant factor, though it is trickier to implement correctly.

It is worth noting that while O(m * n) is often described as quadratic, it is more accurately bilinear. If one string is much shorter than the other, the runtime is effectively linear in the longer string. For example, if n is constant (e.g., searching for a short pattern in a long text), the algorithm runs in O(m) time. This makes the DP approach practical for many real-world scenarios where one string is a query and the other is a document. However, for comparing two very long strings such as entire genomes (millions of characters), O(m * n) becomes infeasible, and linear-time suffix-based methods are required despite their higher implementation complexity.

6. Variations and Optimizations

Beyond the basic DP, several variations and optimizations address specific constraints like memory limits, the need to find all common substrings above a threshold, or handling more than two strings. The most common optimization is the space reduction already discussed, but there are also algorithmic improvements that change the asymptotic complexity or adapt the problem to related tasks. Understanding these variants helps you choose the right tool for the specific problem variant you encounter in practice or in an interview.

One powerful optimization combines binary search with rolling hash (Rabin-Karp). Instead of computing the longest length directly, we ask a decision question: is there a common substring of length k? This can be answered in O(m + n) expected time by hashing all substrings of length k in both strings and checking for intersection using a hash set. Since the predicate "exists common substring of length k" is monotonic (if it exists for k, it exists for all smaller k), we can binary search over k in the range [0, min(m,n)], yielding O((m + n) * log(min(m,n))) time. This is asymptotically faster than DP for large strings and uses linear space, though it is randomized due to hash collisions and requires careful handling of double hashing to avoid false positives.

For the most demanding performance requirements, suffix-based structures provide linear time. A suffix tree or suffix automaton built from the concatenated strings (with a unique separator) can find the longest common substring in O(m + n) time. The idea is to build a generalized suffix tree for both strings and then find the deepest internal node that has leaves from both strings. While theoretically optimal, these structures are complex to implement correctly, have large constant factors, and are rarely expected in coding interviews unless the role is specialized. A suffix array with longest common prefix (LCP) array is a more implementable linearithmic alternative that achieves O((m + n) log(m + n)) time with simpler code.

Handling Multiple Strings and Thresholds

The problem naturally extends to finding the longest common substring among k > 2 strings. The DP recurrence generalizes to k dimensions, but the time and space become O(n^k), which is exponential in k and impractical for k > 3. For multiple strings, suffix-based methods or binary search with hashing are far superior, as they can check for a common substring of length k across all strings by intersecting hash sets iteratively. Another common variant asks for all common substrings with length at least T, rather than just the longest. This can be solved by scanning the DP table for all cells where dp[i][j] >= T and then deduplicating, or more efficiently by using the rolling hash approach to enumerate candidates.

Space optimization can be pushed even further. If you only need the length and not the substring itself, you can use a single array and a variable prev_diag to store the previous diagonal value before it is overwritten. This requires careful ordering: iterate j from 1 to n, save temp = curr[j] before updating, then use prev_diag for the next computation. This reduces memory to exactly min(m,n)+1 integers. Additionally, for very long strings that do not fit in memory, external memory algorithms can process the DP table in blocks, though this is beyond typical interview scope and enters the realm of high-performance computing.

7. Real-World Applications

The longest common substring problem appears in a surprising variety of real-world systems, often hidden beneath higher-level features. In bioinformatics, it is used to identify conserved genetic sequences between species. When comparing DNA strings composed of the alphabet {A, C, G, T}, a long common substring may indicate a functionally important gene region that has been preserved by evolution. Tools like BLAST use heuristics based on common substrings (called seeds) to quickly filter for promising alignments before performing more expensive gapped alignment. The DP solution is often used for moderate-length sequences where exactness is required.

In software engineering, diff tools and version control systems rely heavily on finding common substrings to compute minimal edits. The Unix diff utility, Git's merge algorithm, and plagiarism detectors like MOSS all need to find longest common blocks between files. For plagiarism detection, the system tokenizes source code or natural language and then finds long common substrings that suggest copying. Unlike longest common subsequence, which would allow scattered matching tokens, substring matching ensures the copied text is contiguous, reducing false positives from coincidental common vocabulary. Web search engines also use common substring techniques for near-duplicate detection and for query suggestion by finding common completions.

Other domains include data deduplication in storage systems, where finding common byte sequences allows for efficient compression, and cybersecurity, where signature-based intrusion detection searches for known malicious byte patterns within network traffic. In natural language processing, longest common substring is used for spelling correction, entity matching, and evaluating machine translation quality. Even in databases, fuzzy string matching for record linkage (e.g., matching "Robert Smith" with "Rob Smith") can be framed as finding long common substrings after normalization.

When choosing an algorithm for these applications, engineers must weigh accuracy, speed, and implementation effort. For offline analysis of moderate-sized texts, the DP solution is often sufficient and guarantees correctness. For real-time systems processing millions of strings, such as a web-scale deduplication service, the O(m * n) DP would be too slow, and engineers would opt for suffix automata or hashing-based methods. Understanding the trade-offs allows you to select the right approach for the scale and latency requirements of your system, and to explain that choice convincingly in a system design interview.

8. Comparison with Alternatives

While dynamic programming is the most taught method for longest common substring, it is not the only option. Depending on constraints such as alphabet size, string length, memory limits, and whether you need exact or approximate answers, other algorithms may be more appropriate. This section compares the DP approach with brute force, suffix tree/automaton, suffix array, and binary search with rolling hash across several dimensions to help you make an informed decision.

Brute force is the simplest to implement but the least efficient. It enumerates all substrings of s1 (O(m^2) of them) and checks if each appears in s2 using a naive substring search (O(n) per check), leading to O(m^2 * n) or worse. It is only suitable for very small strings or as a baseline for testing. Suffix trees and suffix automata offer optimal linear time but are notoriously difficult to implement bug-free, especially Ukkonen's algorithm for suffix trees. They also have high memory overhead due to storing many nodes and edges. Suffix arrays are a compromise: they are easier to implement than suffix trees, require less memory, and with an LCP array can solve the problem in O((m+n) log(m+n)) time, which is often fast enough.

Binary search with rolling hash is a practical sweet spot for many engineers. It is relatively easy to implement, runs in O((m+n) log min(m,n)) expected time, and uses linear space. Its main drawback is the probabilistic nature due to hash collisions, though this can be mitigated with double hashing or by verifying candidates with direct comparison. For interview settings, DP is usually expected because it tests understanding of two-dimensional DP without requiring advanced string data structures. However, mentioning these alternatives demonstrates breadth of knowledge and can earn bonus points.

In practice, the choice often depends on the alphabet and the number of strings. For binary or DNA alphabets, suffix automata are particularly efficient. For natural language with large alphabets, hashing works well. If you need to answer many queries about the same pair of strings, building a suffix structure once and answering queries quickly may be worthwhile. For a single query on moderate strings, DP is the pragmatic choice due to its simplicity and determinism. Always consider the constraints given in the problem statement: if m, n ≤ 1000, DP is perfectly fine; if m, n ≤ 10^5, you must mention a linear or log-linear alternative.

9. Common Mistakes and Best Practices

Even though the longest common substring DP is conceptually simple, there are several pitfalls that trap both beginners and experienced developers. The most frequent mistake is confusing it with longest common subsequence and using the wrong recurrence. In subsequence DP, when characters mismatch, you take max(dp[i-1][j], dp[i][j-1]); in substring DP, you must reset to zero. Using the subsequence recurrence will produce an incorrect answer that allows non-contiguous matches, often passing simple tests but failing on cases like "ABC" vs "AC" where the correct substring answer is 1 but the subsequence answer is 2.

Another common error is off-by-one indexing and incorrect substring extraction. Because the DP table is sized (m+1) x (n+1) to handle empty prefixes, the mapping between DP indices and string indices is shifted by one. Forgetting this shift leads to IndexError or incorrect comparisons. Similarly, when extracting the substring after finding max_len and end_pos, using s1[end_pos - max_len : end_pos] is correct only if end_pos is the 1-indexed DP row index. If you store end_pos as a 0-indexed string position, the slice changes. Always test extraction on simple cases like s1="ABC", s2="ABC" to verify you get "ABC" and not "AB" or "BC".

Space optimization introduces its own class of bugs, particularly overwriting the diagonal predecessor. When using a single row or two rows, you must save the value of prev[j-1] before it is overwritten by the current iteration. A classic bug is to update curr[j] = prev[j-1] + 1 and then immediately set prev[j] = curr[j] in the same loop, corrupting the next iteration's diagonal. The correct pattern is to either use two separate arrays and swap them after each row, or use a temporary variable to hold the previous diagonal. Writing a helper to print the DP table and comparing the optimized version's output to the full table's output for random small strings is an excellent way to catch these errors.

Best Practices for Robust Code

To write production-quality code, follow several best practices. First, handle edge cases explicitly at the top of the function: empty strings, None inputs, and strings with no common characters. Return a consistent type, such as a tuple (substring, length) or an empty string with length zero, and document it. Second, choose descriptive variable names like max_len and end_pos rather than single letters, and add comments explaining the meaning of dp[i][j]. Third, if performance matters, ensure you iterate over the shorter string in the inner loop to minimize cache misses and memory usage. Finally, consider Unicode and case sensitivity: decide whether "Hello" and "hello" should match, and normalize strings (e.g., lowercasing) before comparison if needed. Adding unit tests for edge cases like identical strings, completely disjoint strings, and strings with multiple tied answers will prevent regressions.

From an interview perspective, best practices include stating the recurrence before coding, explaining time and space trade-offs, and offering to optimize space if time permits. Start with the clear full-table implementation, verify it works, then discuss how to reduce space. This demonstrates structured problem-solving and communication skills. Also, be prepared to discuss how you would extend the solution to return all longest substrings or to handle k strings, as follow-up questions often probe depth of understanding. Avoid premature optimization: a correct O(m*n) solution is better than a buggy O(m+n) suffix tree attempt.

10. Interview Questions

Longest common substring is a popular interview topic because it tests DP fundamentals, string manipulation, and the ability to distinguish between similar problems. Interviewers often use it to assess whether you can derive a recurrence, analyze complexity, and handle edge cases. Below are common questions and how to approach them effectively, with key points to mention in your answer.

Question 1: Implement a function to find the longest common substring between two strings. What is its time and space complexity? This is the standard question. Start by clarifying whether they want the substring itself or just its length, and whether to return one or all longest substrings. Then describe the DP table definition and recurrence: dp[i][j] = dp[i-1][j-1] + 1 if s1[i-1]==s2[j-1] else 0, with max tracking. Code the full-table version first, then mention the O(min(m,n)) space optimization. State time O(m*n) and space O(m*n) (or O(min(m,n)) optimized), and note that best/average/worst are the same because the full table is always filled.

Question 2: What is the difference between longest common substring and longest common subsequence? Can you solve both with DP? This tests conceptual clarity. Explain that substring requires contiguity while subsequence does not, give an example like "ABCDE" vs "ACE" where subsequence length is 3 but substring length is 1, and contrast the recurrences. For subsequence: if match dp[i][j]=dp[i-1][j-1]+1 else dp[i][j]=max(dp[i-1][j], dp[i][j-1]). For substring: if match dp[i][j]=dp[i-1][j-1]+1 else 0. Emphasize that substring resets on mismatch, while subsequence carries over the best so far. Mention that both have O(m*n) time but different reconstruction methods.

Question 3: How would you optimize the space complexity of your solution? Can you do it in O(min(m,n)) space? Interviewers ask this to see if you understand dependencies. Explain that only the previous row is needed to compute the current row, so two rows suffice. Describe the two-row swap technique and the single-row with diagonal variable technique, and warn about the pitfall of overwriting the diagonal. Provide the optimized code and note that if you need to reconstruct the substring, you still need to track end_pos and max_len, but you do not need the full table. If they ask for all substrings, note that you would need to retain more information or do a second pass.

Question 4: Given two strings up to 10^5 characters, your O(m*n) DP is too slow. How would you find the longest common substring faster? This is a follow-up for senior candidates. Propose binary search with rolling hash (Rabin-Karp) for O((m+n) log min(m,n)) expected time, explaining the monotonic property and hashing all substrings of length k. Alternatively, propose building a suffix automaton or suffix array for O(m+n) linear time, describing the idea of a generalized suffix tree and finding the deepest node with leaves from both strings. Discuss trade-offs: hashing is easier to implement but probabilistic, suffix structures are deterministic but complex. This shows you can think beyond DP and choose algorithms based on constraints.

Question 5: How would you find the longest common substring among three or more strings? This tests generalization. Explain that the k-dimensional DP would be O(n^k) and is infeasible for large k. Propose instead using binary search + hashing: for a given length k, compute hash sets for each string and intersect them, checking if any hash appears in all strings. Or use a generalized suffix tree built from all strings. Mention that the answer length is at most the length of the shortest string, so binary search range is limited. Also note that you could iteratively apply the two-string solution (find LCS of first two, then LCS of that result with third), but this is incorrect because the longest common substring of all three is not necessarily a substring of the LCS of the first two, so a direct multi-string method is required.