Longest Common Substring in DSA Python - Build from Scratch

Longest Common Substring Finder

📖 Scenario: You are working on a text analysis tool that helps find the longest common substring between two given words. This can be useful in spell checkers, plagiarism detectors, or DNA sequence analysis.

🎯 Goal: Build a program that finds the longest common substring between two strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D list (matrix) to store substring lengths

Use nested loops to fill the matrix based on character matches

Track the longest common substring length and its ending index

Print the longest common substring found

💡 Why This Matters

🌍 Real World

Finding longest common substrings is useful in text comparison tools, DNA sequence analysis, and plagiarism detection.

💼 Career

Understanding dynamic programming and string manipulation is essential for software developers working on search engines, bioinformatics, and data analysis.

1

Create the two input strings

Create two string variables called string1 and string2 with the exact values "ABABC" and "BABCA" respectively.

DSA Python

# Your code here

Hint

Use simple assignment to create the two strings exactly as shown.

2

Create the matrix to store substring lengths

Create a 2D list called dp with dimensions len(string1) + 1 by len(string2) + 1, filled with zeros.

DSA Python

string1 = "ABABC"
string2 = "BABCA"
# Your code here

Hint

Use list comprehension to create a matrix of zeros with the correct size.

3

Fill the matrix and find the longest common substring

Use nested for loops with variables i and j starting from 1 to fill dp. When string1[i-1] equals string2[j-1], set dp[i][j] = dp[i-1][j-1] + 1. Track the longest length in max_length and the ending index in end_index.

DSA Python

string1 = "ABABC"
string2 = "BABCA"
dp = [[0] * (len(string2) + 1) for _ in range(len(string1) + 1)]
# Your code here

Hint

Use nested loops starting at 1 because the first row and column are zeros. Update dp[i][j] only when characters match.

4

Print the longest common substring

Print the substring of string1 starting from end_index - max_length up to end_index.

DSA Python

string1 = "ABABC"
string2 = "BABCA"
dp = [[0] * (len(string2) + 1) for _ in range(len(string1) + 1)]
max_length = 0
end_index = 0
for i in range(1, len(string1) + 1):
    for j in range(1, len(string2) + 1):
        if string1[i - 1] == string2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            if dp[i][j] > max_length:
                max_length = dp[i][j]
                end_index = i
# Your code here

Hint

Use slicing on string1 with end_index - max_length as start and end_index as end to get the longest substring.

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