On this page
Description
The longest prefix that every string in a list shares shows up in several places. Autocomplete uses it ("every match starts with 'inter'"). So do grouping routes or keys, and finding the common directory of a set of files. The answer can be no longer than the shortest string, and the best algorithms stop at the first mismatch. This skill covers the column-by-column scan, comparing whole path segments, and the sorting shortcut.
We'll go from simple to more technical:
- The pattern: scan column by column, stopping at the first mismatch.
- A second flavor: compare whole segments for paths and dotted names.
- Where common prefixes show up in production (autocomplete, routing, file trees).
- What breaks it: short strings, unchecked strings, the wrong unit, empty answers.
The approach
Java
String longestCommonPrefix(String[] strs) {
for (int col = 0; ; col++) { // one column at a time
for (String w : strs) {
if (col == w.length() || w.charAt(col) != strs[0].charAt(col)) {
return strs[0].substring(0, col); // first mismatch, or a string ran out
}
}
}
}
Python
def longest_common_prefix(strs: list[str]) -> str:
col = 0
while True: # one column at a time
for w in strs:
if col == len(w) or w[col] != strs[0][col]:
return strs[0][:col] # first mismatch, or a string ran out
col += 1
This vertical scan compares column 0 of every string, then column 1, and stops at the first mismatch or the first string that runs out - at most n * (answer length + 1) character comparisons, never more than the input size. The col == w.length() check must come first: it's what stops the scan at the shortest string instead of running past its end.
The other common version starts with the whole first string and shrinks it until every string starts with it. It's correct, but it can re-compare the same characters over and over: for two 200-character strings that share their first 100, it makes 10,200 character comparisons where the vertical scan makes 202.
A second flavor: compare whole segments
For file paths, a character prefix is the wrong unit: "/a/b" and "/a/bc" share the characters "/a/b", but their common directory is "/a". Split into segments and run the same scan over segments:
Java
String commonDirectory(String[] paths) {
String[] first = paths[0].equals("/") ? new String[0] : paths[0].substring(1).split("/");
int k = first.length; // segments shared so far
for (String p : paths) {
String[] segs = p.equals("/") ? new String[0] : p.substring(1).split("/");
int j = 0;
while (j < k && j < segs.length && first[j].equals(segs[j])) j++;
k = j;
}
return k == 0 ? "/" : "/" + String.join("/", Arrays.copyOf(first, k));
}
Python
def common_directory(paths: list[str]) -> str:
def segments(p: str) -> list[str]:
return [] if p == "/" else p[1:].split("/") # "/".split("/") would be ["", ""]
first = segments(paths[0])
k = len(first) # segments shared so far
for p in paths:
segs = segments(p)
j = 0
while j < k and j < len(segs) and first[j] == segs[j]:
j += 1
k = j
return "/" + "/".join(first[:k]) # "/" when k == 0
Another shortcut: after sorting the strings, the common prefix of the whole list is the common prefix of just the first and last - anything those two extremes share, everything between them shares too.
Where you'll see it
Autocomplete fills in the common prefix of all remaining matches; web routers and key-value stores group keys by shared prefixes (radix trees); build tools find the common root of a set of source files. Python ships both versions: os.path.commonprefix(["/usr/lib", "/usr/local"]) works a character at a time and returns "/usr/l", not a real directory, while os.path.commonpath compares segments and returns "/usr".
Which tool for which job?
| You need | Use |
|---|---|
| Longest common prefix of strings | a vertical scan, stopping at the first mismatch |
The same, written with startsWith | shrink the candidate to the mismatch, not one character at a time |
| Strings already sorted | compare only the first and last |
| Common directory of file paths | normalize, then compare segments |
| Many prefix queries on one set | a trie |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Indexing past the shortest string | an exception | check the length before reading |
| Checking only some strings | a prefix the third string doesn't share | every string |
| Character prefixes of paths | "/a/b" and "/a/bc" give "/a/b" | compare segments ("/a") |
Python's os.path.commonprefix for paths | character-based, the same bug | os.path.commonpath |
| Comparing unnormalized paths | "./" and ".." hide a match | normalize first |
| Shrinking one character at a time | 1,102,551 comparisons instead of 102,051 | chop to the mismatch |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why must the vertical scan check col == w.length() before comparing characters?
Show answer
The shortest string limits the answer. When a string runs out, the prefix can't grow further - and calling charAt(col) on it would throw. Checking the length first also handles an empty string (the answer is "").
2. What's the common directory of "/a/b" and "/a/b/c", and why does a character-level prefix trimmed to the last '/' get it wrong?
Show answer
"/a/b" - it's a directory that contains the other path. The character prefix is "/a/b", and trimming it to the last '/' gives "/a", dropping a segment both paths share. Comparing whole segments avoids guessing where segment boundaries are.
3. After sorting a list of strings, why is the common prefix of the first and last enough?
Show answer
In sorted order, every string lies between the first and the last. If those two share a prefix p, every string between them must also start with p; and any prefix shared by all must be shared by those two.
Key takeaways
- Scan column by column and stop at the first mismatch or the end of the shortest string.
- Shrinking a candidate works but can re-compare characters (10,200 vs 202 comparisons in the example).
- Match the unit to the data: segments for paths, characters for words.
- After sorting, only the first and last strings matter.
- "" and the whole first string are both valid answers.