Longest Common Substring

📋

Problem

Imagine two DNA sequences from different species. Finding the longest common substring helps identify the longest matching genetic segment, which can be crucial for evolutionary studies.

Given two strings s1 and s2, find the length of the longest substring that appears in both strings. A substring is a contiguous sequence of characters within a string. Return the length of this longest common substring.

1 ≤ length of s1, s2 ≤ 10^5Strings consist of lowercase English letters only

Edge cases: One or both strings empty → output 0No common characters at all → output 0Strings are identical → output length of either string

</>

IDE

def longest_common_substring(s1: str, s2: str) -> int:public int longestCommonSubstring(String s1, String s2)int longestCommonSubstring(const string& s1, const string& s2)function longestCommonSubstring(s1, s2)

def longest_common_substring(s1, s2):
    # Write your solution here
    pass

class Solution {
    public int longestCommonSubstring(String s1, String s2) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int longestCommonSubstring(const string& s1, const string& s2) {
    // Write your solution here
    return 0;
}

function longestCommonSubstring(s1, s2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 when strings are identical or have common substrings due to missing DP updates.✅ Update dp[i][j] = dp[i-1][j-1] + 1 when characters match and track max length.

Wrong: 1Greedy approach returning length of first matching character instead of longest substring.✅ Use DP to consider all pairs and track maximum length globally.

Wrong: length of longest common subsequenceConfusing longest common substring with longest common subsequence problem.✅ Reset dp[i][j] to 0 on mismatch; only accumulate when characters match contiguously.

Wrong: crash or exceptionNot handling empty string inputs properly causing index errors.✅ Add base case checks for empty strings and handle dp initialization accordingly.

Wrong: TLEUsing naive O(n*m) DP on large inputs without optimization.✅ Implement more efficient algorithms like suffix automaton or binary search with hashing.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Watch out for tricky cases that break greedy or naive DP implementations.

Optimize your solution to handle large inputs efficiently to avoid timeouts.

t1_01basic

Input{"s1":"abcde","s2":"abfce"}

Expected2

⏱ Performance - must finish in 2000ms

The longest common substring is 'ab' which appears in both strings.

💡 Consider dynamic programming to track matching substrings ending at each index pair.

💡 Use a 2D dp table where dp[i][j] stores length of longest common suffix ending at s1[i-1] and s2[j-1].

💡 Update dp[i][j] = dp[i-1][j-1] + 1 if characters match; track max length found.

Why it failed: Returned incorrect length; likely missed updating dp only when characters match or failed to track max length. Fix by ensuring dp[i][j] = dp[i-1][j-1] + 1 only if s1[i-1] == s2[j-1], else 0.

✓ Correctly computed longest common substring length using DP.

t1_02basic

Input{"s1":"zxabcdezy","s2":"yzabcdezx"}

Expected6

⏱ Performance - must finish in 2000ms

The longest common substring is 'abcdez' with length 6.

💡 Check substrings that appear contiguously in both strings, not just subsequences.

💡 DP approach helps find longest matching suffixes ending at each index pair.

💡 Track max dp[i][j] value to find the longest common substring length.

Why it failed: Incorrect output likely due to treating subsequence instead of substring or not resetting dp[i][j] to 0 on mismatch. Fix by resetting dp[i][j] = 0 when characters differ.

✓ DP correctly identifies longest contiguous matching substring.

t2_01edge

Input{"s1":"","s2":""}

Expected0

⏱ Performance - must finish in 2000ms

Both strings empty; no common substring exists.

💡 Consider base cases where one or both strings are empty.

💡 DP table should handle zero-length strings gracefully.

💡 Return 0 immediately if either string is empty.

Why it failed: Code crashes or returns non-zero for empty strings; fix by adding base case checks for empty inputs returning 0.

✓ Correctly handles empty string inputs returning 0.

t2_02edge

Input{"s1":"a","s2":"a"}

Expected1

⏱ Performance - must finish in 2000ms

Single character strings identical; longest common substring length is 1.

💡 Check behavior with minimal input sizes.

💡 DP initialization must handle single character matches.

💡 Ensure dp updates correctly for single character matches.

Why it failed: Fails to detect single character match; fix by initializing dp properly and checking character equality.

✓ Correctly returns 1 for identical single character strings.

t2_03edge

Input{"s1":"abc","s2":"def"}

Expected0

⏱ Performance - must finish in 2000ms

No common characters; longest common substring length is 0.

💡 Test cases with no common characters should return 0.

💡 DP values reset to 0 on character mismatch.

💡 Max length remains 0 if no matches found.

Why it failed: Returns non-zero when no common substring exists; fix by resetting dp[i][j] to 0 on mismatch and tracking max length correctly.

✓ Correctly returns 0 when no common substring exists.

t3_01corner

Input{"s1":"aaaaa","s2":"aaa"}

Expected3

⏱ Performance - must finish in 2000ms

Longest common substring is 'aaa' of length 3; tests handling of repeated characters.

💡 Repeated characters can cause off-by-one errors in DP indexing.

💡 Ensure dp resets to 0 on mismatch and accumulates correctly on matches.

💡 Track max length carefully to avoid undercounting repeated substrings.

Why it failed: Underestimates length due to off-by-one indexing or failing to accumulate dp values properly. Fix by correctly indexing dp and updating max length on each match.

✓ Correctly handles repeated characters and returns max substring length.

t3_02corner

Input{"s1":"abcxyz","s2":"xyzabc"}

Expected3

⏱ Performance - must finish in 2000ms

Longest common substring is 'xyz' or 'abc' of length 3; tests greedy approach trap.

💡 Greedy approach picking first match may fail here.

💡 DP must consider all pairs and track max length globally.

💡 Do not stop at first match; continue scanning entire dp table.

Why it failed: Greedy approach returns 1 or 0 instead of 3; fix by using DP to track all matches and global max length.

✓ DP correctly finds longest substring despite multiple candidates.

t3_03corner

Input{"s1":"abcd","s2":"abcde"}

Expected4

⏱ Performance - must finish in 2000ms

Longest common substring is 'abcd' at start; tests boundary condition handling.

💡 Check DP initialization at boundaries carefully.

💡 Ensure dp indices align with string indices correctly.

💡 Max length should update when substring starts at index 0.

Why it failed: Fails to detect substring at start due to incorrect dp initialization or indexing. Fix by initializing dp first row and column properly and updating max length.

✓ Correctly detects longest substring at string start boundary.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n*m) DP solution performance; must complete within 2 seconds.

💡 Naive O(n*m) DP may be too slow for max constraints.

💡 Consider optimized algorithms like suffix automaton or binary search with hashing.

💡 Focus on time complexity reduction to avoid TLE.

Why it failed: TLE due to O(n*m) DP approach; fix by implementing more efficient algorithm such as suffix automaton or rolling hash with binary search.

✓ Solution runs within time limit using efficient algorithm.

Practice

1. You need to transform one string into another using the minimum number of insertions, deletions, and substitutions. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic Programming that builds solutions for all prefixes of both strings

B. Greedy algorithm that replaces characters whenever they differ

C. Divide and conquer by splitting strings at midpoint and solving recursively

D. Backtracking all possible sequences of edits without memoization

Solution

1. Step 1: Understand problem requires minimal edits including insertions, deletions, and substitutions

   These operations depend on overlapping subproblems, making DP suitable.

2. Step 2: Identify approach that solves all subproblems efficiently

   Dynamic Programming computes minimal edits for all prefixes, ensuring optimality and polynomial time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP covers all prefix pairs systematically [OK]

Hint: Optimal edit distance requires DP over all prefix pairs [OK]

Common Mistakes:

• Assuming greedy always works
• Thinking divide and conquer alone suffices
• Ignoring overlapping subproblems

2. Consider the following Python code implementing the space-optimized DP solution for maximum uncrossed lines. What is the value of dp after the outer loop completes for i=2 when nums1 = [1,4,2] and nums2 = [1,2,4]?

easy

A. [0, 1, 2, 2]

B. [0, 1, 1, 1]

C. [0, 1, 1, 2]

D. [0, 0, 1, 1]

Solution

1. Step 1: Trace dp after i=1

   For i=1 (nums1[0]=1), dp updates to [0,1,1,1] because nums2 has 1 at j=1, matches increment dp[1].

2. Step 2: Trace dp after i=2

   For i=2 (nums1[1]=4), dp updates as follows: - j=1: no match, dp[1]=max(dp[1], dp[0])=1 - j=2: no match, dp[2]=max(dp[2], dp[1])=1 - j=3: match (4==4), dp[3]=prev+1=1+1=2 where prev is dp[2] before update which was 1, so dp after i=2 is [0,1,1,2].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Matches at positions (1,1) and (2,3) give dp[3]=2 after i=2 [OK]

Hint: Track prev and dp[j] carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing prev and dp[j] updates
• Off-by-one indexing in dp array

3. What is the time complexity of the space-optimized bottom-up DP solution for the Delete Operation for Two Strings problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * log(m + n))

D. O(m^2 + n^2)

Solution

1. Step 1: Identify nested loops over m and n

   The outer loop runs m times, inner loop runs n times, leading to m*n iterations.

2. Step 2: Confirm no extra hidden factors

   Each iteration does O(1) work; no sorting or recursion overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and each cell computed once [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing linear with quadratic
• Assuming sorting or recursion adds log factor
• Ignoring nested loops

4. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Longest Common Subsequence problem, where the input strings have lengths m and n respectively?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify time complexity

   The algorithm uses two nested loops: outer loop runs m times, inner loop runs n times, resulting in O(m*n) time.

2. Step 2: Identify space complexity

   Space optimized DP uses a single array of size n+1, so space complexity is O(n). The recursion stack or full DP table is not used.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops give O(m*n) time; single dp array gives O(n) space [OK]

Hint: Nested loops multiply time; single dp array reduces space [OK]

Common Mistakes:

• Confusing full DP table space with optimized space
• Assuming linear time due to single dp array
• Forgetting recursion stack space in brute force

5. The following code attempts to implement space-optimized DP for regex matching. Which line contains a subtle bug that causes incorrect results on some inputs?

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = False
        for j in range(1, n + 1):
            temp = dp[j]
            if p[j - 1] == '*':
                dp[j] = dp[j] or dp[j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[j] = dp[j] or prev
            else:
                dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])
            prev = temp
    return dp[n]

medium

A. Line: dp[0] = False inside the outer loop

B. Line: for j in range(1, n + 1): iterating forwards instead of backwards

C. Line: prev = dp[0] before inner loop starts

D. Line: dp[j] = dp[j] or dp[j - 2] inside the '*' handling block

Solution

1. Step 1: Understand dp array update dependencies

   When updating dp[j], dp[j - 2] must not be overwritten before use. Iterating forwards overwrites dp[j - 2] too early.

2. Step 2: Identify iteration direction bug

   Iterating forwards causes dp[j - 2] to be stale or overwritten, leading to incorrect matches. Iterating backwards avoids this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Known bug in space-optimized regex DP is forward iteration [OK]

Hint: DP updates with '*' require backward iteration to preserve dp[j-2] [OK]

Common Mistakes:

• Assuming forward iteration is safe in space-optimized DP