Longest Common Substring in DSA Python - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of zeros

↓

For each char in string1

↓

For each char in string2

↓

If chars match

↓

Set table[i

↓

Update max length and end position

↓

After all, extract substring from end position

↓

Return longest common substring

We compare characters of two strings using a 2D table to find the longest matching substring by building lengths from previous matches.

Execution Sample

DSA Python

s1 = "abcde"
s2 = "abfde"

# Build table and find longest common substring

This code builds a table to find the longest common substring between s1 and s2.

Execution Table

Step	Operation	Indices (i,j)	Chars Compared	Table Update	Max Length	End Pos	Visual State
1	Initialize table	-	-	All zeros	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,0]]
2	Compare chars	(1,1)	a vs a	table[1][1] = 1	1	1	[[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]]
3	Compare chars	(1,2)	a vs b	table[1][2] = 0	1	1	[[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]]
4	Compare chars	(1,3)	a vs f	table[1][3] = 0	1	1	[[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]]
5	Compare chars	(1,4)	a vs d	table[1][4] = 0	1	1	[[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]]
6	Compare chars	(1,5)	a vs e	table[1][5] = 0	1	1	[[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]]
7	Compare chars	(2,1)	b vs a	table[2][1] = 0	1	1	[[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]]
8	Compare chars	(2,2)	b vs b	table[2][2] = table[1][1]+1=2	2	2	[[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]]
9	Compare chars	(2,3)	b vs f	table[2][3] = 0	2	2	[[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]]
10	Compare chars	(2,4)	b vs d	table[2][4] = 0	2	2	[[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]]
11	Compare chars	(2,5)	b vs e	table[2][5] = 0	2	2	[[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]]
12	Compare chars	(3,1)	c vs a	table[3][1] = 0	2	2	[[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]]
13	Compare chars	(3,2)	c vs b	table[3][2] = 0	2	2	[[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]]
14	Compare chars	(3,3)	c vs f	table[3][3] = 0	2	2	[[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]]
15	Compare chars	(3,4)	c vs d	table[3][4] = 0	2	2	[[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]]
16	Compare chars	(3,5)	c vs e	table[3][5] = 0	2	2	[[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]]
17	Compare chars	(4,1)	d vs a	table[4][1] = 0	2	2	[[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]]
18	Compare chars	(4,2)	d vs b	table[4][2] = 0	2	2	[[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]]
19	Compare chars	(4,3)	d vs f	table[4][3] = 0	2	2	[[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]]
20	Compare chars	(4,4)	d vs d	table[4][4] = table[3][3]+1=1	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
21	Compare chars	(4,5)	d vs e	table[4][5] = 0	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
22	Compare chars	(5,1)	e vs a	table[5][1] = 0	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
23	Compare chars	(5,2)	e vs b	table[5][2] = 0	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
24	Compare chars	(5,3)	e vs f	table[5][3] = 0	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
25	Compare chars	(5,4)	e vs d	table[5][4] = 0	2	2	[[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,1,0,0],[0,0,0,0,0,0]]
26	Compare chars	(5,5)	e vs e	table[5][5] = table[4][4]+1=2	2	5	[[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,1,0,0],[0,0,0,0,0,2]]
27	End	-	-	-	2	5	Longest substring length 2 ending at s1 index 5

💡 All characters compared, longest common substring length found is 2

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 20	After Step 26	Final
max_length	0	1	2	2	2	2
end_pos	-	1	2	2	5	5
table	all zeros	table[1][1]=1	table[2][2]=2	table[4][4]=1	table[5][5]=2	final table as in visual state

Key Moments - 3 Insights

Why do we add 1 to table[i-1][j-1] when characters match?

Because the current matching characters extend the previous diagonal substring by 1, as shown in steps 8 and 26 where table[i][j] = table[i-1][j-1] + 1.

Why do we only update max_length and end_pos when table[i][j] is greater?

Because max_length tracks the longest substring found so far. We update it only when a longer substring is found, like at steps 8 and 26.

Why is the table initialized with zeros and size (len(s1)+1) x (len(s2)+1)?

The extra row and column of zeros handle the base case for substring length 0, simplifying boundary checks during updates, as seen in step 1.

Visual Quiz - 3 Questions

Look at the execution table at step 8, what is the value of table[2][2]?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'Table Update' column at step 8 in the execution_table.

At which step does the max_length first become 2?

A Step 2

B Step 8

C Step 20

D Step 26

💡 Hint

Look at the 'Max Length' column in execution_table rows to find when it changes to 2.

If the characters at (5,5) did not match, what would be the max_length at the end?

A 1

B 2

C 0

D 3

💡 Hint

Refer to the max_length updates in variable_tracker and execution_table; without the last match, max_length would remain at previous max.

Concept Snapshot

Longest Common Substring finds the longest continuous matching part between two strings.
Use a 2D table where table[i][j] stores length of substring ending at s1[i-1] and s2[j-1].
If chars match, table[i][j] = table[i-1][j-1] + 1, else 0.
Track max length and end position to extract substring after filling table.
Time complexity is O(n*m) for strings of length n and m.
Space complexity is O(n*m) for the table.

Full Transcript

Longest Common Substring compares two strings character by character using a 2D table. Each cell in the table represents the length of the longest substring ending at those positions. When characters match, the value is one plus the diagonal previous cell. We keep track of the maximum length found and where it ends. After filling the table, we extract the substring from the first string using the end position and max length. This method ensures we find the longest continuous matching substring efficiently.

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