A catalog job grouped SKUs by shared prefix so nearby bins stayed in one aisle. A second pass did the same for namespace paths: com.shop.orders and com.shop.payments share com.shop.. The first version walked every pair, shrunk a running prefix, then reduced. A few thousand codes returned in a blink. A million-row dump still finished two long near-matches before a later short string killed the prefix at character zero.

Longest Common Prefix asks for the longest string that sits at the front of every entry. charAt(i) is already free. Pairwise shrinks use that and still re-walk columns you already proved shared. One vertical scan stops at the first column that disagrees.

This is an interview writeup, not a string-layout lecture. We only care about the first mismatch across the list, so the answer is a column walk, not a reduce over every pair.

The problem

Given an array of strings strs, return the longest prefix common to every string. If they share nothing at the front, return "".

strs = ["flower", "flow", "flight"]  →  "fl"
strs = ["dog", "racecar", "car"]     →  ""
strs = [""]                          →  ""

Note: The prefix must be a leading slice of every string, not the longest shared substring somewhere in the middle. "flow" and "wolf" share letters; they do not share a prefix.

Pairwise shrink is the honest brute force

Take the first string as the candidate. For each next string, shrink that candidate until the next string starts with it (or it becomes empty). Correct. You may fully compare two long near-matches before a later entry disagrees at index 0.

String longestCommonPrefixPairwise(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) {
                return "";
            }
        }
    }
    return prefix;
}

At three SKUs this is a rounding error. At a dump where the last path is "z" and the first two are almost identical, you paid two long walks for a question column 0 answers immediately: does every string still agree at this index?

Walk columns until one disagrees

Fix index i on the first string. Scan that same i across every other string. Stop when a string is too short or its character differs. The prefix is strs[0].substring(0, i). If the first string itself is the shared prefix, the outer loop finishes and you return it.

strs = ["flower", "flow", "flight"]

i=0  f  f  f   match
i=1  l  l  l   match
i=2  o  o  i   mismatch → return "fl"

You never finish "flower" against "flow" before looking at "flight". Column 2 is the first disagreement; the walk ends there.

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];
}

Time is O(S) — S is the total number of characters, and the worst case reads every one (all strings equal). Best case stops at the first column. Space is O(1) besides the returned slice.

Note: Index against the first string, then bound-check every other length. A missing i == strs[j].length() is an IndexOutOfBoundsException, not a shorter prefix.

What interviewers usually poke next

  • Empty array. Return "". The length == 0 guard is the whole case; do not dereference strs[0].
  • One string. The inner loop never runs. The outer loop either returns strs[0] or, if that string is empty, returns "". No special branch.
  • Binary search on prefix length. Search lo..hi on the minimum length. Mid is common iff every string starts with strs[0].substring(0, mid). Extra log m factor on the same characters; useful when a startsWith is the only primitive you get, not faster than a vertical scan on the board.
  • Divide and conquer. Prefix of the left half, prefix of the right half, then the prefix of those two. Same O(S) characters, extra stack. Say it, then go back to columns.

You are done with this problem when you can say, out loud, why pairwise shrink is correct, why a vertical scan stops earlier on a late mismatch, and why an empty first string is already "" without a special case.