Longest Common Substring in DSA Python

Mental Model

Find the longest sequence of characters that appears exactly the same and continuously in both strings.

Analogy: Imagine two friends comparing their favorite songs to find the longest part where the lyrics match exactly without breaks.

String1: a b c d e f g
String2: x y b c d z

We look for the longest continuous matching part: b c d

Dry Run Walkthrough

Input: string1: 'abcde', string2: 'abfde'

Goal: Find the longest continuous substring that appears in both strings

Step 1: Initialize a 2D table with zeros for lengths; start comparing characters

Table:
  0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: We need a table to store lengths of matching substrings ending at each position

Step 2: Compare 'a' (string1[0]) and 'a' (string2[0]), they match, set table[1][1] = 1

Table:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: Matching characters start a substring of length 1

Step 3: Compare 'b' (string1[1]) and 'b' (string2[1]), they match, set table[2][2] = table[1][1] + 1 = 2

Table:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: Extend previous matching substring by 1

Step 4: Compare 'c' (string1[2]) and 'f' (string2[2]), no match, set table[3][3] = 0

Table:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: No match breaks the substring continuity

Step 5: Compare 'd' (string1[3]) and 'd' (string2[3]), they match, set table[4][4] = table[3][3] + 1 = 1

Table:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0

Why: New matching substring starts here

Step 6: Compare 'e' (string1[4]) and 'e' (string2[4]), they match, set table[5][5] = table[4][4] + 1 = 2

Table:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 2

Why: Extend the new matching substring by 1

Result:

Longest common substring length is 2, substrings: 'ab' or 'de'

Annotated Code

DSA Python

class Solution:
    def longestCommonSubstring(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_len = 0
        end_index = 0

        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_index = i
                else:
                    dp[i][j] = 0

        return s1[end_index - max_len:end_index]


if __name__ == '__main__':
    s1 = 'abcde'
    s2 = 'abfde'
    sol = Solution()
    result = sol.longestCommonSubstring(s1, s2)
    print(result)

for i in range(1, m + 1):

iterate over each character in first string

for j in range(1, n + 1):

iterate over each character in second string

if s1[i - 1] == s2[j - 1]:

check if characters match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1

extend length of common substring ending here

if dp[i][j] > max_len:

update max length and end position if longer substring found

dp[i][j] = 0

reset length when characters do not match

return s1[end_index - max_len:end_index]

extract longest common substring from first string

Output

ab

Complexity Analysis

Time: O(m*n) because we fill a table comparing each character pair once

Space: O(m*n) because we store lengths for all pairs of positions in both strings

vs Alternative: Naive approach checks all substrings and is O(m*n*min(m,n)) which is slower

Edge Cases

One or both strings empty

Returns empty string as no common substring exists

DSA Python

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

No common substring

max_len remains 0 and empty string is returned

DSA Python

if dp[i][j] > max_len:

Strings are identical

Returns the entire string as longest common substring

DSA Python

dp[i][j] = dp[i - 1][j - 1] + 1

When to Use This Pattern

When asked to find the longest continuous matching part between two strings, use the longest common substring pattern with dynamic programming to track matching lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence (which allows gaps)
Fix: Remember substring requires continuous characters; use dp table resetting to zero on mismatch

Mistake: Not updating max length and end index correctly
Fix: Update max_len and end_index inside the matching condition only when a longer substring is found

Summary

Finds the longest continuous substring common to two strings.

Use when you need the longest exact matching sequence without breaks.

Track lengths of matching substrings ending at each position using a 2D table.

Practice

1. What does the Longest Common Substring problem find between two strings?

easy

A. The total count of matching characters between two strings

B. The longest sequence of characters that appears contiguously in both strings

C. The longest sequence of characters that appears anywhere in both strings, not necessarily contiguous

D. The longest string formed by combining both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters that appears in both strings.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, substrings must be contiguous, so only continuous matching parts count.

3. Final Answer:

   The longest sequence of characters that appears contiguously in both strings -> Option B

4. Quick Check:

   Longest Common Substring = continuous matching part [OK]

Hint: Look for continuous matching parts, not scattered characters [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking order doesn't matter
• Counting non-contiguous matches

2. Which of the following Python code snippets correctly initializes a 2D list for dynamic programming of size (m+1) x (n+1) filled with zeros?

easy

A. dp = [[0] * (m+1)] * (n+1)

B. dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

C. dp = [[0] * (n+1) for _ in range(m+1)]

D. dp = [0] * (m+1) * (n+1)

Solution

1. Step 1: Understand 2D list initialization

   We need a list of lists with (m+1) rows and (n+1) columns filled with zeros.

2. Step 2: Check each option

   dp = [[0] * (n+1) for _ in range(m+1)] uses list comprehension correctly to create independent rows. dp = [[0] * (m+1)] * (n+1) creates shallow copies causing shared rows. dp = [[0 for _ in range(m+1)] for _ in range(n+1)] swaps m and n sizes. dp = [0] * (m+1) * (n+1) creates a flat list, not 2D.

3. Final Answer:

   dp = [[0] * (n+1) for _ in range(m+1)] -> Option C

4. Quick Check:

   Use list comprehension for independent rows [OK]

Hint: Use list comprehension, not multiplication for 2D lists [OK]

Common Mistakes:

• Using multiplication for nested lists causing shared references
• Swapping row and column sizes
• Creating 1D list instead of 2D

3. What is the output of the following Python code that finds the length of the longest common substring between 'abcde' and 'abfde'?

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0
    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
                max_len = max(max_len, dp[i][j])
    return max_len

print(longest_common_substring('abcde', 'abfde'))

medium

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace matching characters

   Comparing 'abcde' and 'abfde': 'a' matches 'a', 'b' matches 'b', 'c' vs 'f' no match, 'd' matches 'd', 'e' matches 'e'. The longest continuous match is 'de' (length 2) at the end, but 'abc' vs 'abf' only matches 'ab' (length 2). However, the longest continuous substring is 'de' (length 2) or 'ab' (length 2). But the code finds the longest continuous substring length, which is 2.

2. Step 2: Confirm longest substring length

   Actually, the longest continuous substring is 'de' or 'ab' both length 2, so the output is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest continuous match = 2 [OK]

Hint: Look for longest continuous matching segment [OK]

Common Mistakes:

• Counting non-continuous matches
• Assuming all matching chars form one substring
• Off-by-one errors in indexing

4. The following code is intended to find the longest common substring length but has a bug. What is the bug?

def lcs_bug(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    max_len = 0
    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
                max_len = max(max_len, dp[i][j])
    return max_len

print(lcs_bug('abc', 'abc'))

medium

A. The character comparison uses wrong indices

B. The loops should start from 0, not 1

C. The max_len is not updated correctly

D. The dp array dimensions are swapped causing index errors

Solution

1. Step 1: Check dp array initialization

   dp is initialized with dimensions (n+1) x (m+1), but loops use i in [1..m], j in [1..n], causing index mismatch.

2. Step 2: Identify impact of swapped dimensions

   Accessing dp[i][j] where i can be up to m and j up to n will cause index errors or incorrect results because dp rows and columns are swapped.

3. Final Answer:

   The dp array dimensions are swapped causing index errors -> Option D

4. Quick Check:

   dp size must match loop indices [OK]

Hint: Match dp size with loop variable ranges [OK]

Common Mistakes:

• Swapping row and column sizes in dp
• Starting loops at 0 causing index errors
• Not updating max_len inside condition

5. Given two strings s1 = 'ababc' and s2 = 'babca', which of the following Python functions correctly returns the longest common substring itself (not just length)?

hard

A. def lcs_string(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
end = 0
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 = i
return s1[end-max_len:end]

B. def lcs_string(s1, s2):
return max(set(s1) & set(s2))

C. def lcs_string(s1, s2):
return s1 if s1 in s2 else ''

D. def lcs_string(s1, s2):
return ''.join([c for c in s1 if c in s2])

Solution

1. Step 1: Analyze def lcs_string(s1, s2): m, n = len(s1), len(s2) dp = [[0]*(n+1) for _ in range(m+1)] max_len = 0 end = 0 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 = i return s1[end-max_len:end] logic

   def lcs_string(s1, s2): m, n = len(s1), len(s2) dp = [[0]*(n+1) for _ in range(m+1)] max_len = 0 end = 0 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 = i return s1[end-max_len:end] uses dynamic programming to track lengths of matching substrings and records the end index of the longest one, then slices s1 to return it.

2. Step 2: Check other options for correctness

   def lcs_string(s1, s2): return max(set(s1) & set(s2)) returns a single character, not substring. def lcs_string(s1, s2): return s1 if s1 in s2 else '' returns s1 only if fully contained in s2. def lcs_string(s1, s2): return ''.join([c for c in s1 if c in s2]) returns all matching chars concatenated, not continuous substring.

3. Final Answer:

   Option A correctly returns the longest common substring -> Option A

4. Quick Check:

   DP with end index tracks substring [OK]

Hint: Track end index and max length to slice substring [OK]

Common Mistakes:

• Returning only length, not substring
• Using set intersection losing order and continuity
• Concatenating matching chars ignoring continuity