Longest Common Prefix
Asked at Google, Meta, Oracle, Walmart
Problem
Find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string. This problem tests string manipulation and can be solved with vertical scanning, binary search, or a trie.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Oracle | Easy | View all Oracle questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
Vertical scanning: take the first string as a reference. For each character position i, check if every other string has the same character at position i. Stop at the first mismatch. This is O(S) where S is the sum of all characters.
Why vertical scanning works: if the first string is "flower" and the second is "flow", compare character by character: f==f, l==l, o==o, w!=w... wait, "flower" and "flow" share "flo". At position 3, "flower" has 'w' and "flow" has 'w' -- actually they match. Position 4: "flower" has 'e', "flow" is out of bounds. Stop. Prefix = "flow".
Visual walkthrough for ["flower", "flow", "flight"]:
Pos 0: f, f, f -> all match
Pos 1: l, l, l -> all match
Pos 2: o, o, i -> mismatch! Stop.
Prefix = "fl"
Alternative: binary search on prefix length. The prefix can be at most as long as the shortest string. Check if the first half of that length is a common prefix. If yes, check the second half. This is O(S * log n) where n is the length of the shortest string.
The trie approach: insert all strings into a trie. Walk down from the root -- a node with only one child means the prefix continues. A node with multiple children means the prefix stops. This is elegant but overkill for an interview.
Edge cases: empty array returns "". Array with one string returns that string. No common prefix at all (first characters differ) returns "". Strings of different lengths -- prefix stops at the shortest one.
Optimal Approach
Step 1: If the array is empty, return "".
Step 2: Use the first string as the reference.
Step 3: For each character position i in the first string:
- Check every other string at position i
- If any string is shorter than i, or any string has a different character at i, stop
Step 4: Return the prefix up to (but not including) position i.
Walkthrough for ["flower", "flow", "flight"]:
- Reference: "flower" (length 6)
- i=0: all strings have 'f' at index 0. Continue.
- i=1: all strings have 'l' at index 1. Continue.
- i=2: "flower" has 'o', "flow" has 'o', "flight" has 'i'. Mismatch! Stop.
- Return "fl" (first 2 characters).
Time: O(S) where S is the sum of all characters across all strings. In the worst case, we check every character. Space: O(1) -- we only store the prefix index.
What Trips People Up in Real Interviews
Building a full trie for an interview. While correct, it's overkill. Vertical scanning is simpler, faster to code, and shows you can find the right tool for the job. Save trie for when the interviewer asks for a follow-up.
Sorting the array first to compare only the first and last strings. This works (O(n * k log n)) but is slower than vertical scanning (O(S)). Interviewers will ask why you sorted when a linear scan suffices.
Forgetting to handle strings of different lengths. If the reference string is longer than another string, you'll get an index out of bounds. Always check i < len(other_string) before comparing characters.
Using the first string as reference when a shorter string exists. While correct, consider using the shortest string as the reference to minimize comparisons. This is a micro-optimization but shows attention to detail.
Not handling the edge case where all strings are identical. In this case, the prefix is the entire shortest string. Make sure your loop completes without early termination and returns the full string.
Solution Code
def longestCommonPrefix(strs):
if not strs:
return ""
for i, ch in enumerate(strs[0]):
for s in strs[1:]:
if i >= len(s) or s[i] != ch:
return strs[0][:i]
return strs[0]Frequently Asked Questions
What is the Longest Common Prefix problem?
Find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string. This problem tests string manipulation and can be solved with vertical scanning, `binary search`, or a `trie`.
How do you solve Longest Common Prefix?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Common Prefix?
Longest Common Prefix is asked at Google, Meta, Oracle, Walmart. It is a easy difficulty problem.
What are common mistakes on Longest Common Prefix?
- Building a full `trie` for an interview. While correct, it's overkill. Vertical scanning is simpler, faster to code, and shows you can find the right tool for the job. Save `trie` for when the interviewer asks for a follow-up.
- Sorting the array first to compare only the first and last strings. This works (`O(n * k log n)`) but is slower than vertical scanning (`O(S)`). Interviewers will ask why you sorted when a linear scan suffices.
- Forgetting to handle strings of different lengths. If the reference string is longer than another string, you'll get an index out of bounds. Always check `i < len(other_string)` before comparing characters.
- Using the first string as reference when a shorter string exists. While correct, consider using the shortest string as the reference to minimize comparisons. This is a micro-optimization but shows attention to detail.
- Not handling the edge case where all strings are identical. In this case, the prefix is the entire shortest string. Make sure your loop completes without early termination and returns the full string.