Longest Common Prefix in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

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

DSA C++

std::string longestCommonPrefix(std::vector<std::string>& strs) {
    if (strs.empty()) return "";
    std::string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    std::vector<std::string> words = {"flower", "flow", "flight"};
    std::cout << longestCommonPrefix(words);
    return 0;
}

A ""

B "flow"

C "f"

D "fl"

💡 Hint

Check how the prefix is shortened when it doesn't match the start of each string.

The function starts with the first string as the prefix. It then compares this prefix with each subsequent string. If the current string does not start with the prefix, the prefix is shortened by one character from the end until it matches or becomes empty. For the input {"flower", "flow", "flight"}, the longest common prefix is "fl".

🧠 Conceptual

intermediate

Longest Common Prefix Concept

Which of the following best describes the longest common prefix of a list of strings?

A The longest substring that appears anywhere in all strings.

B The longest substring that appears at the end of all strings.

C The longest substring that appears at the start of all strings.

D The longest substring that appears in at least one string.

💡 Hint

Think about the position where the substring must appear in all strings.

The longest common prefix is the longest substring that appears at the beginning (start) of all strings in the list.

❓ Predict Output

advanced

Output of Vertical Scanning Method

What is the output of this C++ code using vertical scanning to find the longest common prefix?

DSA C++

std::string longestCommonPrefix(std::vector<std::string>& strs) {
    if (strs.empty()) return "";
    for (int i = 0; i < strs[0].size(); i++) {
        char c = strs[0][i];
        for (int j = 1; j < strs.size(); j++) {
            if (i == strs[j].size() || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
}

int main() {
    std::vector<std::string> words = {"interview", "interrupt", "integrate", "integral"};
    std::cout << longestCommonPrefix(words);
    return 0;
}

A "int"

B "inte"

C "inter"

D "integ"

💡 Hint

Check character by character vertically until a mismatch or string end.

The function compares characters at each position across all strings. The first mismatch occurs at position 4 (0-based index), so the prefix is the first 4 characters "inte".

🔧 Debug

advanced

Identify the Error in Longest Common Prefix Code

What error does the following C++ code produce when trying to find the longest common prefix?

DSA C++

std::string longestCommonPrefix(std::vector<std::string>& strs) {
    if (strs.empty()) return "";
    std::string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

A Runtime error: out_of_range exception

B Compilation error: missing semicolon

C Logical error: returns empty string always

D No error, runs correctly

💡 Hint

Check the loop boundary condition accessing vector elements.

The for loop uses i <= strs.size(), which causes access to strs[strs.size()] (out of bounds), leading to a runtime out_of_range exception.

🚀 Application

expert

Longest Common Prefix in Large Dataset

You have 1 million strings each of length up to 1000 characters. Which approach is most efficient to find the longest common prefix?

A Sorting the list and comparing only the first and last strings

B Vertical scanning by checking characters column-wise across all strings

C Horizontal scanning by comparing prefix with each string sequentially

D Divide and conquer by splitting the list and merging prefixes

💡 Hint

Consider minimizing comparisons by leveraging sorted order.

Sorting the list places strings with similar prefixes together. The longest common prefix of the whole list is the prefix common to the first and last strings after sorting, reducing comparisons drastically.

Practice

1. What does the Longest Common Prefix (LCP) problem ask you to find given a list of strings?

easy

A. The total count of common characters in all strings

B. The longest starting substring common to all strings

C. The longest ending substring common to all strings

D. The longest substring common to any two strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix means the longest substring at the start of all strings that is the same.

2. Step 2: Compare options with the definition

   Only The longest starting substring common to all strings matches the definition exactly: longest starting substring common to all strings.

3. Final Answer:

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

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

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

Common Mistakes:

• Confusing prefix with substring anywhere
• Thinking about suffix instead of prefix
• Counting characters instead of substring

2. Which of the following C++ code snippets correctly initializes a vector of strings named strs with values "flower", "flow", "flight"?

easy

A. std::vector strs = {"flower", "flow", "flight"};

B. std::vector strs = {"flower", "flow", "flight"};

C. vector<string> strs = ("flower", "flow", "flight");

D. std::vector strs = ("flower", "flow", "flight");

Solution

1. Step 1: Check correct vector initialization syntax

   In C++, to initialize a vector of strings with values, use curly braces {} and specify type with std::vector.

2. Step 2: Validate each option

   std::vector strs = {"flower", "flow", "flight"}; uses correct syntax with std::vector and braces {}. Versions missing std:: namespace, using parentheses instead of braces, or lacking template type <std::string> are invalid.

3. Final Answer:

   std::vector strs = {"flower", "flow", "flight"}; -> Option A

4. Quick Check:

   Correct vector initialization uses braces and type [OK]

Hint: Use curly braces {} and full type for vector initialization [OK]

Common Mistakes:

• Using parentheses instead of braces
• Omitting std:: namespace
• Missing template argument

3. What is the output of the following C++ code?

std::vector strs = {"interview", "internet", "internal"};
std::string prefix = strs[0];
for (int i = 1; i < strs.size(); i++) {
    int j = 0;
    while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {
        j++;
    }
    prefix = prefix.substr(0, j);
}
std::cout << prefix << std::endl;

medium

A. int

B. inte

C. intern

D. inter

Solution

1. Step 1: Initialize prefix and compare with each string

   Start prefix = "interview". Compare with "internet": common prefix is "inter". Update prefix = "inter".

2. Step 2: Compare updated prefix "inter" with "internal"

   Common prefix is "inter" again. So prefix remains "inter".

3. Final Answer:

   inter -> Option D

4. Quick Check:

   Common prefix of all = "inter" [OK]

Hint: Compare prefix with each string, shorten prefix on mismatch [OK]

Common Mistakes:

• Stopping after first comparison
• Not updating prefix correctly
• Confusing substring indices

4. Identify the bug in the following C++ code that tries to find the longest common prefix:

std::string longestCommonPrefix(std::vector& strs) {
    std::string prefix = strs[0];
    for (int i = 1; i < strs.size(); i++) {
        int j = 0;
        while (j < prefix.size() && j < strs[i].size() && prefix[j] == strs[i][j]) {
            j++;
        }
        prefix = prefix.substr(0, j);
        if (prefix.empty()) return "";
    }
    return prefix;
}

// Usage:
// std::vector words = {"dog", "racecar", "car"};
// std::cout << longestCommonPrefix(words) << std::endl;

medium

A. The function does not handle empty input vector

B. The function returns incorrect prefix for input {"dog", "racecar", "car"}

C. The while loop condition is incorrect and causes infinite loop

D. The function should return the longest common suffix instead

Solution

1. Step 1: Check empty input handling

   The code directly accesses strs[0] without checking if strs is empty, causing a runtime error (out-of-range access) for empty vectors.

2. Step 2: Verify other statements

   The loop logic correctly shortens the prefix, no infinite loop occurs, it returns prefix not suffix, and for {"dog", "racecar", "car"} it correctly returns "".

3. Final Answer:

   The function does not handle empty input vector -> Option A

4. Quick Check:

   Missing if(strs.empty()) return ""; [OK]

Hint: Test edge cases like empty lists first [OK]

Common Mistakes:

• Overlooking empty vector handling
• Misjudging the output for no common prefix cases
• Suspecting infinite loop in the while condition

5. Given a list of strings {"apple", "ape", "april", "apt"}, write a C++ function to find the longest common prefix using a vertical scanning approach. What will be the output of your function?

hard

A. "app"

B. "a"

C. "ap"

D. ""

Solution

1. Step 1: Understand vertical scanning approach

   Check characters column by column across all strings until mismatch or end of any string.

2. Step 2: Apply vertical scanning on given strings

   Index 0: all have 'a'. Index 1: all have 'p'. Index 2: "apple" has 'p', "ape" has 'e' (mismatch). Stop scanning.

3. Final Answer:

   "ap" -> Option C

4. Quick Check:

   Vertical scan stops at first mismatch, prefix = "ap" [OK]

Hint: Scan characters column-wise until mismatch found [OK]

Common Mistakes:

• Assuming prefix is longest word's start
• Stopping scan too early or too late
• Confusing vertical with horizontal scanning