Longest Common Substring in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Substring Length Calculation

What is the output of the following Python code that calculates the length of the longest common substring between two strings?

DSA Python

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("abcdef", "zcdemf"))

A 3

B 2

C 4

D 1

💡 Hint

Look for the longest sequence of matching characters in order.

The longest common substring between "abcdef" and "zcdemf" is "cde" which has length 3.

❓ Predict Output

intermediate

Longest Common Substring Result String

What is the output of this code that returns the longest common substring itself (not just length)?

DSA Python

def longest_common_substring_str(s1, s2):
    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
    return s1[end_index - max_len:end_index]

print(longest_common_substring_str("banana", "ananas"))

A "nan"

B "ana"

C "ana" and "nan" both appear but only one is longest

D "anana"

💡 Hint

Check which substring appears continuously in both strings.

The longest common substring between "banana" and "ananas" is "anana" which has length 5.

🧠 Conceptual

advanced

Understanding Dynamic Programming Table for Longest Common Substring

In the dynamic programming table used for longest common substring, what does the value dp[i][j] represent?

A Length of longest common substring ending at s1[i-1] and s2[j-1]

B Length of longest common substring anywhere in s1[:i] and s2[:j]

C Length of longest common subsequence ending at s1[i-1] and s2[j-1]

D Length of longest common subsequence anywhere in s1[:i] and s2[:j]

💡 Hint

Focus on the substring ending exactly at those positions.

dp[i][j] stores the length of the longest common substring that ends exactly at s1[i-1] and s2[j-1]. It resets to zero if characters don't match.

🔧 Debug

advanced

Identify the Error in Longest Common Substring Code

What error will this code produce when run?

DSA Python

def lcs_wrong(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * n for _ in range(m)]
    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_wrong("abc", "abc"))

A SyntaxError

B Returns 0

C IndexError: list index out of range

D TypeError: unsupported operand type(s) for +: 'int' and 'str'

💡 Hint

Check how dp is initialized and accessed.

dp is initialized with size m x n but accessed with indices up to m and n inclusive, causing IndexError.

🚀 Application

expert

Longest Common Substring in Multiple Strings

Given three strings, which approach correctly finds the longest common substring among all three?

A Find longest common substring of first two strings, then find longest common substring of that result with the third string

B Find longest common substring of all three strings simultaneously using a 3D DP table

C Find longest common subsequence of all three strings and treat it as substring

D Find longest common substring of first and third strings, then check if it appears in second string

💡 Hint

Consider how to track substring matches across three strings at once.

To find longest common substring among three strings, a 3D DP table is needed to track substring matches ending at each position in all three strings simultaneously.

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