Longest Common Substring in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Substring problem?

It is the problem of finding the longest sequence of characters that appears in the same order and contiguously in two given strings.

intermediate

How does the dynamic programming approach help solve the Longest Common Substring problem?

It builds a table where each cell represents the length of the longest common suffix of substrings ending at those positions, allowing us to find the maximum length efficiently.

intermediate

In Rust, which data structure is commonly used to store the DP table for Longest Common Substring?

A 2D vector (Vec) is used to store lengths of common suffixes for substrings of the two input strings.

beginner

What is the time complexity of the dynamic programming solution for Longest Common Substring?

The time complexity is O(m * n), where m and n are the lengths of the two input strings.

beginner

Why is Longest Common Substring different from Longest Common Subsequence?

Longest Common Substring requires the matching characters to be contiguous, while Longest Common Subsequence allows characters to be non-contiguous but in order.

What does each cell in the DP table represent in the Longest Common Substring problem?

A Length of longest common subsequence

B Length of longest common prefix starting at those positions

C Length of longest common suffix ending at those positions

D Total number of matching characters so far

Each DP cell stores the length of the longest common suffix of substrings ending at the current indices.

What is the main difference between Longest Common Substring and Longest Common Subsequence?

A Subsequence requires contiguous characters, substring does not

B Substring is always longer than subsequence

C They are the same problem

D Substring requires contiguous characters, subsequence does not

Longest Common Substring requires characters to be contiguous; subsequence allows gaps.

What is the time complexity of the DP solution for Longest Common Substring?

A O(m * n)

B O(m^2 * n^2)

C O(m + n)

D O(log(m + n))

The DP table has size m by n, so the solution runs in O(m * n) time.

Which Rust data structure is best suited for the DP table in Longest Common Substring?

A Vec<Vec<usize>>

B HashMap<String, usize>

C LinkedList<usize>

D Array of Strings

A 2D vector (Vec>) efficiently stores the DP table values.

If two strings have no common substring, what is the longest common substring length?

A 1

B 0

C Length of shorter string

D Length of longer string

No common substring means the longest common substring length is zero.

Explain how to use dynamic programming to find the Longest Common Substring between two strings.

Think about comparing characters and building on previous results.

Describe the difference between Longest Common Substring and Longest Common Subsequence with examples.

Focus on whether characters must be next to each other.

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