Longest Common Substring in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D list for dynamic programming.

DSA Python

dp = [[0] * (len(s2) + 1) for _ in [1]]

Drag options to blanks, or click blank then click option'

Arange(len(s1) + 1)

Blen(s1)

Crange(len(s2))

Dlen(s2) + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using length of s2 instead of s1 for rows

Not adding 1 for empty substring

We create a 2D list with rows equal to length of s1 + 1 to include empty substring cases.

2fill in blank

medium

Complete the code to update the dp table when characters match.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aj

Bi - 1

Cj - 1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i-1][j] or dp[i][j-1] instead of dp[i-1][j-1]

Mixing up i and j indices

We look diagonally up-left in the dp table at dp[i-1][j-1] to extend the substring length.

3fill in blank

hard

Fix the error in the code that resets dp when characters do not match.

DSA Python

else:
    dp[i][j] = [1]

Drag options to blanks, or click blank then click option'

A1

Bdp[i][j - 1]

Cdp[i - 1][j]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Copying previous dp values instead of resetting

Setting to 1 incorrectly

When characters don't match, the longest common substring ending here is zero.

4fill in blank

hard

Fill both blanks to update the maximum length and ending index of the substring.

DSA Python

if dp[i][j] > [1]:
    max_len = dp[i][j]
    end_index = [2]

Drag options to blanks, or click blank then click option'

Amax_len

Bi

Cj

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i-1 for end index

Not updating max_len correctly

Update max_len if current dp value is greater, and store the ending index as i-1 (string index).

5fill in blank

hard

Fill all three blanks to return the longest common substring from s1.

DSA Python

return s1[[1] - [2] + 1 : [3] + 1]

Drag options to blanks, or click blank then click option'

Aend_index

Bmax_len

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing start and end indices

Off-by-one errors in slicing

The substring starts at end_index - max_len + 1 and ends at end_index (inclusive).

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