Longest Common Prefix in DSA Rust - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

Compare prefix with next string

↓

Find common prefix between prefix and current string

↓

Update prefix to this common prefix

↓

More strings?

Yes→Repeat comparison

No↓

Return prefix

Start with the first string as the prefix. Compare it with each string to find the common prefix. Update the prefix each time. Stop when no more strings or prefix is empty.

Execution Sample

DSA Rust

fn longest_common_prefix(strs: &[&str]) -> String {
    if strs.is_empty() { return "".to_string(); }
    let mut prefix = strs[0];
    for s in strs.iter().skip(1) {
        while !s.starts_with(prefix) {
            prefix = &prefix[..prefix.len()-1];
            if prefix.is_empty() {
                return "".to_string();
            }
        }
    }
    prefix.to_string()
}

This code finds the longest common prefix among a list of strings by shrinking the prefix until it matches all strings.

Execution Table

Step	Operation	Current Prefix	String Compared	Prefix Update	Visual State
1	Initialize prefix	"flower"	N/A	"flower"	[flower]
2	Compare prefix with "flow"	"flower"	"flow"	"flow" does not start with prefix, shrink prefix	[flower]
3	Shrink prefix	"flower"	"flow"	"flowe"	[flowe]
4	"flow" still does not start with prefix, shrink	"flowe"	"flow"	"flow"	[flow]
5	"flow" starts with prefix, move to next string	"flow"	"flow"	"flow"	[flow]
6	Compare prefix with "flight"	"flow"	"flight"	"flight" does not start with prefix, shrink prefix	[flow]
7	Shrink prefix	"flow"	"flight"	"flo"	[flo]
8	"flight" does not start with prefix, shrink	"flo"	"flight"	"fl"	[fl]
9	"flight" starts with prefix, move to next string	"fl"	"flight"	"fl"	[fl]
10	No more strings, return prefix	"fl"	N/A	"fl"	[fl]

💡 All strings compared, prefix is "fl" which is the longest common prefix

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 9	Final
prefix	"flower"	"flower"	"flow"	"flow"	"flo"	"fl"	"fl"
current_string	N/A	"flow"	"flow"	"flow"	"flight"	"flight"	N/A

Key Moments - 3 Insights

Why do we shrink the prefix instead of moving to the next string immediately?

Because the prefix must be common to all strings so far. If the current prefix is not a start of the current string (see steps 2-4), we shrink it until it matches or becomes empty.

What happens if the prefix becomes empty during shrinking?

If prefix becomes empty, it means no common prefix exists. The loop would end and the function returns an empty string. This is implied in the shrinking loop (step 4).

Why do we start prefix with the first string?

Starting with the first string ensures the prefix is at most as long as any string. We then reduce it to fit all strings. This is shown in step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the prefix after step 4?

A "flowe"

B "flow"

C "flo"

D "fl"

💡 Hint

Check the 'Prefix Update' column at step 4 in the execution table.

At which step does the prefix first become "fl"?

A Step 7

B Step 9

C Step 8

D Step 10

💡 Hint

Look at the 'Prefix Update' column and find when prefix is set to "fl".

If the input list was empty, what would the function return?

A Empty string

B The first string

C Panic or error

D The last string

💡 Hint

Refer to the code line: if strs.is_empty() { return "".to_string(); }

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- Compare prefix with each string
- Shrink prefix until it matches start of string
- Stop when all strings checked or prefix empty
- Return prefix as longest common prefix

Full Transcript

Longest Common Prefix finds the longest starting substring common to all strings in a list. We start with the first string as the prefix. For each next string, we check if it starts with the prefix. If not, we shrink the prefix by removing the last character until it matches or becomes empty. We repeat this for all strings. If prefix becomes empty, no common prefix exists. Finally, we return the prefix. This method ensures the prefix is always common to all strings processed so far.

Practice

1. What does the Longest Common Prefix (LCP) of a list of strings represent?

easy

A. The shortest string in the list

B. The longest substring found anywhere in all strings

C. The longest starting substring common to all strings

D. The last character of the longest string

Solution

1. Step 1: Understand the prefix concept

   A prefix is a substring starting at the beginning of a string.

2. Step 2: Define longest common prefix

   The longest common prefix is the longest substring starting at the beginning that all strings share.

3. Final Answer:

   The longest starting substring common to all strings -> Option C

4. Quick Check:

   Prefix means start of strings = A [OK]

Hint: Focus on start of strings, not anywhere inside [OK]

Common Mistakes:

• Confusing prefix with substring anywhere
• Choosing shortest string instead of common start
• Thinking prefix is the last part of strings

2. Which Rust code snippet correctly initializes a vector of strings for finding the longest common prefix?

easy

A. let words = vec!["flower", "flow", "flight"];

B. let words = ["flower", "flow", "flight"];

C. let words = vec!("flower", "flow", "flight");

D. let words = vec<str>["flower", "flow", "flight"];

Solution

1. Step 1: Identify correct vector initialization syntax

   In Rust, vec![...] creates a vector with elements inside square brackets.

2. Step 2: Check syntaxes

   vec![...] is correct. [...] without vec! creates an array, not a vector. vec!() uses incorrect parentheses. vec<str>[...] is invalid syntax.

3. Final Answer:

   let words = vec!["flower", "flow", "flight"]; -> Option A

4. Quick Check:

   vec![...] is correct vector syntax [OK]

Hint: Use vec![...] to create vectors in Rust [OK]

Common Mistakes:

• Using parentheses instead of square brackets in vec!
• Confusing arrays with vectors
• Incorrect generic syntax for vec

3. What is the output of this Rust code that finds the longest common prefix?

fn longest_common_prefix(strs: Vec<&str>) -> String {
    if strs.is_empty() { return String::new(); }
    let mut prefix = strs[0].to_string();
    for s in &strs[1..] {
        while !s.starts_with(&prefix) {
            prefix.pop();
            if prefix.is_empty() { return String::new(); }
        }
    }
    prefix
}

fn main() {
    let words = vec!["interview", "internet", "internal"];
    println!("{}", longest_common_prefix(words));
}

medium

A. "int"

B. "inter"

C. "in"

D. "internal"

Solution

1. Step 1: Initialize prefix with first string

   Prefix starts as "interview".

2. Step 2: Compare prefix with second string "internet"

   "internet".starts_with("interview") is false, so pop last char repeatedly: pop 'w' -> "intervie" (false), pop 'e' -> "intervi" (false), pop 'i' -> "interv" (false), pop 'v' -> "inter" (true, since "internet".starts_with("inter")).

3. Step 3: Compare prefix "inter" with third string "internal"

   "internal".starts_with("inter") is true, so prefix remains "inter".

4. Final Answer:

   "inter" -> Option B

5. Quick Check:

   Common start is "inter" = B [OK]

Hint: Shrink prefix until all strings start with it [OK]

Common Mistakes:

• Not shrinking prefix correctly
• Assuming full first string is prefix
• Confusing substring anywhere with prefix

4. Identify the bug in this Rust function for longest common prefix and select the fix:

fn longest_common_prefix(strs: Vec<&str>) -> String {
    if strs.is_empty() { return String::new(); }
    let mut prefix = strs[0].to_string();
    for s in &strs[1..] {
        while !s.starts_with(prefix) {
            prefix.pop();
            if prefix.is_empty() { return String::new(); }
        }
    }
    prefix
}

medium

A. Change s.starts_with(prefix) to s.starts_with(&prefix)

B. Replace prefix.pop() with prefix.remove(0)

C. Initialize prefix as empty string instead of strs[0]

D. Add a break statement inside the while loop

Solution

1. Step 1: Identify type mismatch in starts_with

   starts_with expects a &str reference, but prefix is String. Passing prefix directly causes type error.

2. Step 2: Fix by passing reference to prefix

   Use &prefix to pass a &str reference, matching function signature.

3. Final Answer:

   Change s.starts_with(prefix) to s.starts_with(&prefix) -> Option A

4. Quick Check:

   Use & prefix for &str parameter [OK]

Hint: Pass &String as &str in starts_with [OK]

Common Mistakes:

• Passing String instead of &str to starts_with
• Removing first char instead of last char
• Not checking empty prefix before popping

5. Given a list of strings, write a Rust function that returns the longest common prefix but ignores case differences (case-insensitive). Which approach is best?

hard

A. Reverse strings and find prefix from the end

B. Compare characters using ASCII values directly

C. Use starts_with without modification

D. Convert all strings to lowercase before finding prefix

Solution

1. Step 1: Understand case-insensitive comparison

   To ignore case, convert all strings to the same case (lowercase or uppercase) before comparison.

2. Step 2: Apply lowercase conversion before prefix logic

   Transform each string to lowercase, then find longest common prefix normally.

3. Final Answer:

   Convert all strings to lowercase before finding prefix -> Option D

4. Quick Check:

   Normalize case first for case-insensitive prefix [OK]

Hint: Normalize case before prefix check [OK]

Common Mistakes:

• Comparing characters without case normalization
• Using ASCII values without case mapping
• Reversing strings which doesn't solve case issue