Longest Common Substring in DSA Rust

Mental Model

Find the longest sequence of characters that appears exactly the same in both strings without skipping any characters.

Analogy: Imagine two friends reading two different books and trying to find the longest exact sentence that appears in both books without any changes or gaps.

String1: a b c d e f g
String2: x y b c d z

We look for the longest matching continuous part: b c d

Dry Run Walkthrough

Input: string1: "abcde", string2: "abfde"

Goal: Find the longest substring that appears in both strings exactly and continuously

Step 1: Compare characters at positions (0,0): 'a' and 'a' match, set length to 1

DP matrix partial:
[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]

Why: Matching characters start a common substring of length 1

Step 2: Compare characters at positions (1,1): 'b' and 'b' match, length becomes 2

DP matrix partial:
[1,0,0,0,0]
[0,2,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]

Why: Extending the previous substring by one character

Step 3: Compare characters at positions (2,2): 'c' and 'f' do not match, length reset to 0

DP matrix partial:
[1,0,0,0,0]
[0,2,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]

Why: Mismatch breaks the substring continuity

Step 4: Compare characters at positions (4,4): 'e' and 'e' match, length is 1

DP matrix partial:
[1,0,0,0,0]
[0,2,0,0,0]
[0,0,0,0,0]
[0,0,0,0,0]
[0,0,0,0,1]

Why: New matching substring starts at the end

Result:

Longest common substring length is 2, substring is "ab"

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    pub fn longest_common_substring(s1: &str, s2: &str) -> (usize, String) {
        let bytes1 = s1.as_bytes();
        let bytes2 = s2.as_bytes();
        let m = bytes1.len();
        let n = bytes2.len();
        let mut dp = vec![vec![0; n + 1]; m + 1];
        let mut max_len = 0;
        let mut end_index = 0;

        for i in 1..=m {
            for j in 1..=n {
                if bytes1[i - 1] == bytes2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // extend previous substring length
                    if dp[i][j] > max_len {
                        max_len = dp[i][j]; // update max length
                        end_index = i; // track end position in s1
                    }
                }
            }
        }

        let start = end_index - max_len;
        let substring = s1[start..end_index].to_string();
        (max_len, substring)
    }
}

fn main() {
    let s1 = "abcde";
    let s2 = "abfde";
    let (length, substring) = Solution::longest_common_substring(s1, s2);
    println!("Longest common substring length: {}", length);
    println!("Longest common substring: {}", substring);
}

if bytes1[i - 1] == bytes2[j - 1] {

check if current characters match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1;

extend length of common substring by 1 from previous diagonal

if dp[i][j] > max_len {

update max length and end index if current substring is longer

Output

Longest common substring length: 2

Longest common substring: ab

Complexity Analysis

Time: O(m*n) because we compare each character of first string with each character of second string once

Space: O(m*n) because we store lengths of common substrings for all pairs of positions

vs Alternative: Naive approach checks all substrings which is O(m^2*n^2), so DP is much faster

Edge Cases

One or both strings empty

Returns length 0 and empty substring

DSA Rust

let m = bytes1.len(); let n = bytes2.len();

No common substring

Returns length 0 and empty substring

DSA Rust

if bytes1[i - 1] == bytes2[j - 1] {

Strings are identical

Returns full string length and the string itself

DSA Rust

max_len = dp[i][j]; end_index = i;

When to Use This Pattern

When asked to find the longest continuous matching part between two strings, use the longest common substring pattern with dynamic programming to track matching lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence (which allows gaps)
Fix: Remember substring must be continuous; use DP with diagonal checks, not separate subsequence logic

Summary

Finds the longest continuous matching substring between two strings.

Use when you need exact continuous matches, not skipping characters.

Track matching lengths diagonally in a DP matrix to find the longest substring.

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