Longest Common Substring in DSA Rust - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of size (len(s1)+1) x (len(s2)+1)

↓

Initialize all cells to 0

↓

For each character in s1 (i)

↓

For each character in s2 (j)

↓

If s1[i-1

Yes↓

Set table[i

↓

Update max length and position if needed

No↓

Set table[i

↓

After filling table, extract substring from s1 using max length and position

↓

Return longest common substring

We compare characters of two strings using a 2D table to find the longest matching substring by building lengths of matching suffixes step-by-step.

Execution Sample

DSA Rust

fn longest_common_substring(s1: &str, s2: &str) -> String {
    let m = s1.len();
    let n = s2.len();
    let mut table = vec![vec![0; n + 1]; m + 1];
    let mut max_len = 0;
    let mut end_pos = 0;

    for i in 1..=m {
        for j in 1..=n {
            if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
                table[i][j] = table[i - 1][j - 1] + 1;
                if table[i][j] > max_len {
                    max_len = table[i][j];
                    end_pos = i;
                }
            } else {
                table[i][j] = 0;
            }
        }
    }

    s1[end_pos - max_len..end_pos].to_string()
}

This code finds the longest common substring between two strings by filling a 2D table with lengths of matching suffixes.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	Table[i][j] Value	Max Length	End Position	Visual Table State (partial)
1	Initialize table	-	-	All zeros	0	0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
2	Compare s1[0] and s2[0]	(1,1)	'a' vs 'b'	0	0	0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
3	Compare s1[0] and s2[1]	(1,2)	'a' vs 'a'	1	1	1	[[0,0,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]
4	Compare s1[0] and s2[2]	(1,3)	'a' vs 'c'	0	1	1	[[0,0,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]]
5	Compare s1[1] and s2[0]	(2,1)	'b' vs 'b'	1	1	2	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]]
6	Compare s1[1] and s2[1]	(2,2)	'b' vs 'a'	0	1	2	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]]
7	Compare s1[1] and s2[2]	(2,3)	'b' vs 'c'	0	1	2	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]]
8	Compare s1[2] and s2[0]	(3,1)	'c' vs 'b'	0	1	2	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]]
9	Compare s1[2] and s2[1]	(3,2)	'c' vs 'a'	0	1	2	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]]
10	Compare s1[2] and s2[2]	(3,3)	'c' vs 'c'	1	1	3	[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]]
11	End of loops	-	-	-	1	3	Final table filled
12	Extract substring	-	-	-	-	-	Substring s1[2..3] = 'c'

💡 All characters compared; longest common substring length found and substring extracted.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 10	Final
max_len	0	1	1	1	1
end_pos	0	1	2	3	3
table[1][2]	0	1	1	1	1
table[2][1]	0	0	1	1	1
table[3][3]	0	0	0	1	1

Key Moments - 3 Insights

Why do we start indices i and j from 1 instead of 0 in the table?

Because the table has an extra row and column at index 0 to represent empty prefixes, so actual string characters start from index 1. This is shown in execution_table rows where i and j start at 1.

Why do we set table[i][j] to 0 when characters don't match?

Because the longest common substring must be continuous, so if characters differ, the matching length resets to 0 at that position. This is seen in execution_table rows where mismatches set table[i][j] to 0.

How do we know which substring to extract after filling the table?

We track max_len and end_pos whenever we find a longer match. After loops, we extract substring from s1 using end_pos - max_len to end_pos, as shown in execution_table step 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of table[1][2]?

A 1

B 0

C 2

D Undefined

💡 Hint

Check the 'Table[i][j] Value' column in execution_table row 3.

At which step does max_len first update to 1?

A Step 2

B Step 3

C Step 5

D Step 10

💡 Hint

Look at the 'Max Length' column in execution_table rows 2 and 3.

If s1[2] was 'd' instead of 'c', what would be the value of table[3][3] at step 10?

A 1

B 0

C 2

D Undefined

💡 Hint

Compare characters at s1[2] and s2[2] in execution_table step 10 and see what happens when they don't match.

Concept Snapshot

Longest Common Substring:
- Use 2D table of size (m+1)x(n+1) for strings s1 and s2
- table[i][j] = length of longest suffix 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 during fill
- Extract substring from s1 using max length and end position

Full Transcript

Longest Common Substring finds the longest continuous matching part between two strings. We create a 2D table where each cell shows the length of matching suffixes ending at those positions. We fill the table by comparing characters of both strings. If they match, we add 1 to the diagonal cell's value; if not, we reset to 0. 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 recorded position and 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 longest sequence of characters that appears in both strings consecutively

B. The longest sequence of characters that appears in both strings but not necessarily consecutively

C. The total number of common characters between two strings

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 without interruption.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, which allows gaps, Longest Common Substring requires characters to be consecutive.

3. Final Answer:

   The longest sequence of characters that appears in both strings consecutively -> Option A

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

Hint: Look for continuous matching characters in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking characters can be non-consecutive
• Counting total common characters instead of longest sequence

2. Which Rust code snippet correctly initializes a 2D vector for dynamic programming in Longest Common Substring?

easy

A. let mut dp = vec![vec![0; n + 1]; m + 1];

B. let dp = vec![vec![0; m]; n];

C. let mut dp = vec![vec![0; m + 1]; n];

D. let dp = vec![vec![0; n]; m + 1];

Solution

1. Step 1: Understand dimensions for DP table

   For strings of length m and n, dp table size should be (m+1) x (n+1) to include empty prefixes.

2. Step 2: Check Rust vector initialization syntax

   vec![vec![0; n + 1]; m + 1] creates m+1 rows each with n+1 zeros, matching DP table size.

3. Final Answer:

   let mut dp = vec![vec![0; n + 1]; m + 1]; -> Option A

4. Quick Check:

   DP table size = (m+1) x (n+1) [OK]

Hint: DP table size = (length+1) for both strings [OK]

Common Mistakes:

• Swapping m and n in vector sizes
• Forgetting +1 for empty string row/column
• Using immutable vector when mutability is needed

3. What is the output of this Rust code snippet for strings s1 = "abcde" and s2 = "abfde"?

let s1 = "abcde";
let s2 = "abfde";
let m = s1.len();
let n = s2.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
let mut max_len = 0;
for i in 1..=m {
    for j in 1..=n {
        if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if dp[i][j] > max_len {
                max_len = dp[i][j];
            }
        }
    }
}
println!("{}", max_len);

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Compare characters and fill DP table

   Matching characters are 'a' and 'b' at start, then 'd' and 'e' at the end. The longest continuous match is "ab" with length 2.

2. Step 2: Track max_len during iteration

   max_len updates to 1 for 'a', then 2 for 'b', resets for mismatch, then 1 for 'd' and 1 for 'e'. So max_len = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Longest common substring length = 2 [OK]

Hint: Check consecutive matches, longest is "ab" length 2 [OK]

Common Mistakes:

• Counting non-consecutive matches
• Confusing substring length with subsequence length
• Ignoring reset of dp on mismatch

4. Identify the bug in this Rust code snippet for Longest Common Substring:

let s1 = "hello";
let s2 = "yellow";
let m = s1.len();
let n = s2.len();
let mut dp = vec![vec![0; n]; m];
let mut max_len = 0;
for i in 1..=m {
    for j in 1..=n {
        if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if dp[i][j] > max_len {
                max_len = dp[i][j];
            }
        }
    }
}
println!("{}", max_len);

medium

A. Loop ranges should start from 0, not 1

B. DP vector size is incorrect; should be (m+1) x (n+1)

C. Comparison should use chars(), not as_bytes()

D. max_len should be initialized to 1, not 0

Solution

1. Step 1: Check DP vector initialization

   DP vector is initialized with size m x n, but loops access dp[i][j] with i and j starting at 1, causing out-of-bounds error.

2. Step 2: Correct DP vector size

   DP vector should be sized (m+1) x (n+1) to safely access dp[i][j] for i and j in 1..=m and 1..=n.

3. Final Answer:

   DP vector size is incorrect; should be (m+1) x (n+1) -> Option B

4. Quick Check:

   DP size must match loop indices [OK]

Hint: DP size = (length+1) to avoid index errors [OK]

Common Mistakes:

• Using wrong DP vector size causing panic
• Starting loops at 0 but indexing with i-1
• Confusing bytes and chars for comparison

5. Given two strings s1 = "ababc" and s2 = "babca", write a Rust function to find the longest common substring and return it. What is the correct longest common substring?

hard

A. "bab"

B. "babc"

C. "abca"

D. "abc"

Solution

1. Step 1: Use DP to find longest common substring length and end index

   By comparing characters and updating dp, the longest common substring length is 3, ending at index 4 in s1.

2. Step 2: Extract substring from s1 using end index and length

   Substring of length 3 ending at index 4 in s1 is "abc".

3. Final Answer:

   "abc" -> Option D

4. Quick Check:

   Longest common substring = "abc" length 3 [OK]

Hint: Track max length and end index, then slice substring [OK]

Common Mistakes:

• Choosing substring from wrong string
• Confusing substring with subsequence
• Not updating end index when max length changes