Longest Common Prefix in DSA Rust

Mental Model

Find the longest starting part that all words share exactly the same letters in order.

Analogy: Imagine several friends starting a race together and running side by side. The longest common prefix is like the distance they all run together before anyone speeds up or slows down.

words: [flower, flow, flight]
indexes:  0 1 2 3 4 5 6
          f l o w e r
          f l o w
          f l i g h t
prefix:  ↑ ↑

Dry Run Walkthrough

Input: words: [flower, flow, flight]

Goal: Find the longest prefix all words share at the start

Step 1: Start with the first word 'flower' as the prefix

prefix = 'flower'

Why: We need a starting point to compare with others

Step 2: Compare prefix 'flower' with second word 'flow', shorten prefix to match

prefix = 'flow'

Why: The second word is shorter and only matches first 4 letters

Step 3: Compare prefix 'flow' with third word 'flight', shorten prefix to match

prefix = 'fl'

Why: Only first 2 letters match with 'flight'

Result:

prefix = 'fl'
Answer: 'fl'

Annotated 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.iter().skip(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);
}

let mut prefix = strs[0].to_string();

initialize prefix with first word to start comparisons

for s in strs.iter().skip(1) {

iterate over remaining words to compare prefix

while !s.starts_with(&prefix) {

reduce prefix until it matches the start of current word

prefix.pop();

remove last character from prefix to shorten it

if prefix.is_empty() { return String::new(); }

if prefix is empty, no common prefix exists, return empty string

Output

fl

Complexity Analysis

Time: O(S) because in worst case we compare all characters of all strings once

Space: O(1) because prefix is stored in place and no extra large structures are used

vs Alternative: Compared to checking all pairs or building tries, this method is simpler and uses less memory

Edge Cases

empty list of words

returns empty string immediately

DSA Rust

if strs.is_empty() { return String::new(); }

no common prefix at all

prefix shortens to empty and returns empty string

DSA Rust

if prefix.is_empty() { return String::new(); }

all words are the same

returns the full word as prefix

DSA Rust

prefix initialized to first word and never shortened

When to Use This Pattern

When you need to find the longest shared start among many strings, use the longest common prefix pattern to compare and shorten step by step.

Common Mistakes

Mistake: Not checking if the list is empty before accessing first element
Fix: Add a guard to return empty string if input list is empty

Mistake: Comparing characters one by one manually instead of using starts_with
Fix: Use built-in starts_with method to simplify prefix matching

Mistake: Not shortening prefix correctly leading to infinite loop
Fix: Pop last character from prefix inside the loop until match or empty

Summary

Finds the longest starting substring common to all strings in a list.

Use when you want to find shared beginnings in multiple words or strings.

Start with the first word as prefix and shorten it until all words start with it.

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