Longest Common Prefix in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

What is the output of the following Rust code that finds the longest common prefix of a list of strings?

DSA Rust

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!["flower", "flow", "flight"];
    let result = longest_common_prefix(words);
    println!("{}", result);
}

A "f"

B "flow"

C "fl"

D ""

💡 Hint

Check the common starting letters of all words until a mismatch occurs.

The longest common prefix among "flower", "flow", and "flight" is "fl" because all three start with 'f' and 'l', but differ after that.

❓ Predict Output

intermediate

Longest Common Prefix with Empty String Present

What will be printed by this Rust program that finds the longest common prefix when one string is empty?

DSA Rust

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!["dog", "", "dove"];
    let result = longest_common_prefix(words);
    println!("{}", result);
}

A "d"

B "dog"

C "do"

D ""

💡 Hint

An empty string means no common prefix longer than empty string.

Since one string is empty, the longest common prefix must be empty as no characters are common at the start.

🧠 Conceptual

advanced

Behavior of Longest Common Prefix Algorithm

Which statement best describes how the longest common prefix algorithm works in the given Rust code?

DSA Rust

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
}

A It starts with the first string as prefix and shortens it until all strings start with it.

B It compares characters one by one for all strings simultaneously.

C It sorts the strings and compares only the first and last strings.

D It uses recursion to find the prefix by dividing the list.

💡 Hint

Look at how the prefix variable is updated inside the loop.

The code initializes prefix as the first string, then shortens it by removing last characters until all strings start with it.

🔧 Debug

advanced

Identify the Error in Longest Common Prefix Code

What error will this Rust code produce when trying to find the longest common prefix?

DSA Rust

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
}

A Type mismatch error because prefix is String but starts_with expects &str

B Index out of bounds error when prefix is empty

C No error, code runs correctly

D Borrow checker error due to mutable and immutable borrow conflict

💡 Hint

Check the argument type passed to starts_with method.

starts_with expects a string slice (&str), but prefix is a String. Passing prefix directly causes a type mismatch error.

🚀 Application

expert

Longest Common Prefix Result for Large Input

Given a vector of 100,000 strings where each string is "abcde" repeated 10 times, except the last string which is "abcdf" repeated 10 times, what is the longest common prefix returned by the Rust function?

DSA Rust

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 mut words = vec!["abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde"; 99999];
    words.push("abcdfabcdfabcdfabcdfabcdfabcdfabcdfabcdfabcdfabcdf");
    let result = longest_common_prefix(words);
    println!("{}", result);
}

A "abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde"

B "abcd"

C ""

D "abc"

💡 Hint

Check where the first mismatch occurs between the last string and others.

The last string differs at the 5th character ('e' vs 'f'), so the common prefix stops before that character, resulting in "abcd".

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