PPractick

The problem

A command-line tool offers tab completion: when several filenames match what the user has typed, it fills in as many characters as all of them share. That's the longest common prefix of a list of strings. The straightforward way compares the strings column by column until some string runs out or disagrees. A neat alternative sorts the list and compares only the first and last strings, because they're the most different.

Example: ["flower", "flow", "flight"] → "fl".

Function signature

string longestCommonPrefix(const vector<string>& strs);  // strs is non-empty

Test cases

Input strs	Output	Explanation
["flower", "flow", "flight"]	"fl"
["dog", "racecar", "car"]	""	They differ at the first character
["interview", "internet", "interval", "internal"]	"inter"
["a"]	"a"	A single string is its own prefix
["", "b"]	""	An empty string limits the prefix
["abc", "abc"]	"abc"	Identical strings

(Confirm: the list is non-empty; strings may be empty; comparison is case-sensitive.)

How interviewers phrase it

• "Find the longest common prefix among an array of strings" (LeetCode 14).
• Sometimes a lead-in to tries (Step 17 of the sheet), which answer prefix queries efficiently.

Clarifying questions to ask

1. Can the list be empty? Can strings be empty?
2. Case-sensitive?
3. How many strings and how long? (Affects which approach is best.)

Follow-ups to expect

1. "What's the vertical scanning approach?"
2. "How does sorting help?"
3. "What about divide and conquer or binary search on the length?"
4. "When would a trie be better?"
5. "Complexity?"

Related questions

• Check if String is Palindrome or Not Easy
• Largest Odd Number in a String Easy
• Isomorphic String Easy
• Rotate String Easy
• Check if two strings are anagram of each other Easy
• Sort Characters by Frequency Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in