Longest Common Prefix in DSA C++

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 turns or stops.

words: [flower, flow, flight]
common prefix: [fl] ↑

Dry Run Walkthrough

Input: words: [flower, flow, flight]

Goal: Find the longest prefix string that is common to all words

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

prefix = 'flower'
words = [flower, flow, flight]

Why: We need a starting point to compare with other words

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

prefix = 'flow'
words = [flower, flow, flight]

Why: The prefix must be common to both words, so we cut it down to 'flow'

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

prefix = 'fl'
words = [flower, flow, flight]

Why: Only 'fl' matches at the start of both 'flow' and 'flight'

Result:

prefix = 'fl'
Answer: 'fl'

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";  // handle empty input
    string prefix = strs[0];  // start with first word as prefix
    for (int i = 1; i < (int)strs.size(); i++) {
        // shorten prefix until it matches the start of strs[i]
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.size() - 1);  // remove last char
            if (prefix.empty()) return "";  // no common prefix
        }
    }
    return prefix;
}

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

if (strs.empty()) return "";

handle empty input list by returning empty prefix

string prefix = strs[0];

initialize prefix with first word

for (int i = 1; i < (int)strs.size(); i++) {

iterate over remaining words to compare prefix

while (strs[i].find(prefix) != 0) {

reduce prefix until it matches start of current word

prefix = prefix.substr(0, prefix.size() - 1);

remove last character from prefix to shorten it

if (prefix.empty()) return "";

if prefix is empty, no common prefix exists

Output

fl

Complexity Analysis

Time: O(S) where S is the sum of all characters in all words because we compare characters until mismatch

Space: O(1) because we only store the prefix string and no extra data structures proportional to input size

vs Alternative: Compared to checking character by character for all words simultaneously, this approach reduces repeated comparisons by shrinking prefix progressively

Edge Cases

empty list of words

returns empty string immediately

DSA C++

if (strs.empty()) return "";

list with one word

returns the word itself as prefix

DSA C++

string prefix = strs[0];

no common prefix at all

prefix shrinks to empty and returns empty string

DSA C++

if (prefix.empty()) return "";

When to Use This Pattern

When you need to find the longest starting substring common to many strings, use the Longest Common Prefix pattern to progressively shorten a candidate prefix.

Common Mistakes

Mistake: Comparing characters of all words at each position without early stopping
Fix: Use the first word as prefix and shorten it when mismatch found instead of checking all characters repeatedly

Mistake: Not handling empty input list causing runtime errors
Fix: Add a check at start to return empty string if input list is empty

Summary

Finds the longest starting substring common to all input strings.

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

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

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