Longest Common Prefix
Find the longest string that every word in a list starts with. A simple column-by-column scan that stops at the first mismatch or the shortest word. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Given an array of strings strs, return the longest string that is a prefix of every string in the array.
If the strings don't all share a first character, return the empty string "".
Example 1
- Input
- strs = ["interval", "internet", "interior"]
- Output
- "inter"
All three start with "inter". The next characters are "v", "n" and "i", which differ.
Example 2
- Input
- strs = ["stack", "queue"]
- Output
- ""
The first characters already differ.
Example 3
- Input
- strs = ["react"]
- Output
- "react"
A single string is its own longest common prefix.
Constraints
- 1 ≤ strs.length ≤ 200
- 0 ≤ strs[i].length ≤ 200
- strs[i] contains only lowercase English letters.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Longest Common Prefix in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Longest Common Prefix
Pattern: Vertical scan
Line the strings up on top of each other and read down the columns. The common prefix is every column, from the left, where all strings have the same character. The first column where one string differs, or where some string has already ended, is where the prefix stops.
That's the whole problem. The main things to get right are the stopping conditions: a mismatch, or running past the end of the shortest string. The answer can never be longer than the shortest string, so the work is bounded by n × (shortest length), not by the longest string.
Approach 1: Horizontal: shrink a running prefix
Start with prefix = strs[0]. For each other string, chop characters off the end of prefix until the string starts with it. Easy to write, but every startsWith check rescans the prefix, so a long first string that is cut down slowly does extra work.
Time O(S), where S is the total characters · Space O(1) beyond the prefix
Approach 2: Sort and compare the ends
After sorting, the first and last strings are the most different, so their common prefix is everyone's common prefix. Neat, but sorting costs O(n log n) string comparisons.
Time O(n log n · m) · Space O(n) for the sort
Approach 3: Vertical scan
For each index i in strs[0]:
- Let
ch = strs[0][i]. - For every other string
s, ifi == len(s)ors[i] != ch, returnstrs[0][:i].
If the loop finishes, strs[0] itself is the answer. It stops at the first mismatching column, so it never reads more than n × (prefix length + 1) characters.
Time O(S) worst case, often much less · Space O(1) beyond the answer
| Approach | Time | Space |
|---|---|---|
| Horizontal: shrink a running prefix | O(S), where S is the total characters | O(1) beyond the prefix |
| Sort and compare the ends | O(n log n · m) | O(n) for the sort |
| Vertical scan | O(S) worst case, often much less | O(1) beyond the answer |
Solution code
Try the practice editor first. Both solutions pass every test above.
Longest Common Prefix solution in Python
def longest_common_prefix(strs: list[str]) -> str:
first = strs[0]
for i, ch in enumerate(first):
for s in strs[1:]:
if i == len(s) or s[i] != ch:
return first[:i]
return firstLongest Common Prefix solution in JavaScript
function longestCommonPrefix(strs) {
const first = strs[0];
for (let i = 0; i < first.length; i++) {
const ch = first[i];
for (let j = 1; j < strs.length; j++) {
if (i === strs[j].length || strs[j][i] !== ch) return first.slice(0, i);
}
}
return first;
}Common mistakes
- Reading `s[i]` past the end of a shorter string. Python raises an IndexError; JavaScript quietly gives `undefined`.
- Forgetting that an empty string anywhere in the list makes the answer empty.
- Building the prefix with repeated string concatenation in a language where that copies, turning the scan quadratic.
- Returning `strs[0]` without checking that every other string actually starts with it.
What interviewers look for
This is a warm-up, so the interviewer is mostly checking that you're careful. State the stopping conditions (mismatch or end of a string) before coding, and mention that the answer is bounded by the shortest string.
If you have time, compare the horizontal and vertical scans: the vertical one stops as soon as any column fails, which matters when a single short string or an early mismatch would end the search. Mention the sort trick as an alternative, but explain why it isn't faster.
Follow-up questions
What if you get many queries asking for the longest common prefix of a query string with the list?
Build a trie of the strings once, storing at each node how many strings pass through it. For a query, walk the trie while the count equals the total number of strings and the characters match; each query then costs O(query length).
Can you find it with binary search?
Yes. Binary search on the prefix length L between 0 and the shortest length, checking whether every string starts with strs[0][:L]. That is O(S log m), which is not better here but shows the monotonic structure: if a length-L prefix is shared, every shorter one is too.
How would you split the work across machines?
Divide and conquer: compute the common prefix of each chunk independently, then combine chunks by taking the common prefix of their answers. The operation is associative, so it reduces cleanly.
Companies that ask Longest Common Prefix
Longest Common Prefix is tagged by 124 companies in our interview dataset. The score shows how often it comes up at each company.
- Dxc Technology100%
- Kraken Technologies100%
- Lightmatter100%
- Revolut100%
- Disney100%
- Usaa100%
- Cme Group96.6%
- Yelp94.2%
- Commscope93%
- Sailpoint91%
- Persistent Systems89.4%
- Target88.2%
- Ihs Markit88%
- Oyo87.9%
- Wipro87.5%
- Apptio85%
- SAP84.4%
- Opentext83.6%
- PwC83.3%
- Epam Systems83.1%
- Hsbc81.3%
- Unacademy81%
- Nokia80.4%
- Thryv80%
and 100 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required