Why Longest Common Substring in DSA Python?

The Big Idea

What if you could instantly find the longest exact match between two texts without endless guessing?

The Scenario

Imagine you have two long texts and you want to find the longest part that appears exactly the same in both. Doing this by reading and comparing every possible part by hand would take forever and be very tiring.

The Problem

Manually checking every possible substring is slow and confusing. You might miss some matches or make mistakes because there are so many parts to compare. It's like trying to find a needle in a haystack without any tools.

The Solution

The Longest Common Substring method quickly finds the longest matching part between two texts by using a smart way to compare them. It saves time and avoids mistakes by checking all possibilities systematically.

Before vs After

✗ Before

text1 = 'abcdef'
text2 = 'zabcf'
# Manually check all substrings one by one
# Very slow and error-prone

✓ After

def longest_common_substring(text1, text2):
    # Use dynamic programming to find longest common substring
    # Fast and reliable

What It Enables

This lets you quickly find the longest exact matching part between two texts, enabling tasks like plagiarism detection, DNA sequence analysis, and more.

Real Life Example

When checking if two documents share a long copied paragraph, the Longest Common Substring helps find that exact copied part quickly and accurately.

Key Takeaways

Manual substring comparison is slow and error-prone.

Longest Common Substring uses a smart method to find matches fast.

This helps in many real-world tasks like text and DNA analysis.

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