14. Longest Common Prefix

Compare the strings column by column: at each character position, every string must share the same character. Stop at the first column where they disagree or some string ends — everything before that is the common prefix.

Idea

The common prefix can't be longer than the shortest string, and it must match every string at every position up to its length. Scanning vertically — one character column at a time across all strings — lets us stop the instant any string diverges, without comparing whole strings repeatedly.

Algorithm

1. Take the first string as a reference. For each character index i of it:
   • For every other string s: if i reaches len(s) or s[i] differs from the reference character, the prefix ends at i — return the first i characters.
2. If we never diverge, the whole first string is the prefix.

(Equivalently: shrink a candidate prefix until every string starts with it.)

Worked example: ["flower","flow","flight"]

• Column 0: f, f, f ✓. Column 1: l, l, l ✓. Column 2: o, o, i ✗ — flight diverges.

Common prefix = "fl".

Complexity

• Time: O(S) where S is the total number of characters across all strings (worst case).
• Space: O(1).

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