Longest Common Prefix in DSA C++ - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

Compare prefix with next string

↓

Find common prefix between prefix and string

↓

Update prefix

↓

More strings?

Yes→Repeat comparison

No↓

Return prefix

Start with the first string as the prefix. Compare it with each next string to update the prefix to the common part. Stop when no more strings or prefix is empty.

Execution Sample

DSA C++

string longestCommonPrefix(vector<string>& strs) {
  if (strs.empty()) return "";
  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;
}

This code finds the longest common prefix among all strings in the list by shrinking the prefix until it matches the start of each string.

Execution Table

Step	Operation	Current Prefix	String Compared	Prefix Update	Visual State
1	Initialize prefix	flower	-	prefix = 'flower'	flower
2	Compare prefix with 'flow'	flower	flow	prefix shrinks to 'flow'	flow
3	Compare prefix with 'flight'	flow	flight	prefix shrinks to 'fl'	fl
4	No more strings	fl	-	Return prefix 'fl'	fl

💡 All strings compared or prefix became minimal; final prefix is 'fl'

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
prefix	flower	flow	fl	fl
i	0	1	2	2

Key Moments - 3 Insights

Why do we shrink the prefix inside a while loop?

Because the prefix might not match the start of the current string, so we keep removing the last character until it does, as shown in step 2 and 3 of the execution_table.

What if the prefix becomes empty?

If prefix becomes empty, it means no common prefix exists. The loop stops and returns an empty string. This is implied in the while loop condition in the code.

Why start prefix with the first string?

Starting with the first string ensures the prefix is initially the longest possible. Then it shrinks as needed, as shown in step 1 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the prefix after comparing with the second string?

A flower

B flow

C fl

D flight

💡 Hint

Check the 'Current Prefix' and 'Prefix Update' columns at step 2 in execution_table.

At which step does the prefix become 'fl'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Current Prefix' column in execution_table for step 3.

If the third string was 'flowerpot' instead of 'flight', what would the prefix be after step 3?

A flow

B fl

C flower

D flig

💡 Hint

Compare the prefix update logic in execution_table and imagine 'flowerpot' starts with 'flow'.

Concept Snapshot

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

Full Transcript

Longest Common Prefix finds the longest starting substring common to all strings. We start with the first string as the prefix. Then for each next string, we check if it starts with the prefix. If not, we remove the last character from the prefix and check again. We repeat until the prefix matches the start of the string or becomes empty. After processing all strings, the prefix is the longest common prefix. The code uses a while loop inside a for loop to shrink the prefix as needed. The execution table shows how the prefix changes step by step with example strings 'flower', 'flow', and 'flight'.

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