Longest Common Prefix

EASY✓ CHIP-TIMEDLC #14 — FULL STATEMENT ↗

The drill: Every word in the list opens with some shared run of characters — possibly empty. Measure exactly how far that agreement stretches before the first word breaks ranks.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of strings arrives, and hidden inside them is some shared run of characters that every single one starts with — the job is to measure exactly how long that shared opening is.

The moment any string in the list disagrees with the others at some position, the shared prefix stops there; the result reports everything up to but not including that break.

If the strings share nothing from the very first character, the answer is an empty string — that's a perfectly valid outcome, not a failure case that needs special handling.

EX 01

strs = ["training", "trail", "train"]

→ "trai"

SPLITS AT THE FIFTH COLUMN

EX 02

strs = ["pace", "pacer", "paces"]

→ "pace"

THE SHORTEST WORD IS THE PREFIX

EX 03

strs = ["fartlek", "tempo", "surge"]

→ ""

NO AGREEMENT AT COLUMN ZERO

the list holds at least one string
strings may vary widely in length, including empty ones
lowercase letters only, on this course
the result is empty when there is no shared opening across all strings

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The answer can never outlast the shortest word, and one disagreement anywhere caps it for good. What's the cheapest way to find the FIRST disagreement?

HINT 2 THE STRUCTURE

Compare column by column instead of word by word: position 0 across every word, then position 1, and so on. The first column that isn't unanimous ends the prefix.

HINT 3 ONE STEP FROM THE ANSWER

Walk the first word's characters; at index i, any other word that is only i long or differs there marks the cut. Survive the whole walk and the entire first word is the answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

COLUMN BY COLUMNPATTERN · COLUMN SCANstrs = ["training", "trail", "train"]

STEP 1

Three words: training, trail, train. Walk column by column until one word disagrees.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-common-prefix.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]
        for i, ch in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != ch:
                    return first[:i]    # first non-unanimous column
        return first

TIME O(N·M)SPACE O(1)PYTHON · RACE PACE · 8 LN

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = strs[0]
        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]    # chop until this word accepts it
                if not prefix:
                    return ""
        return prefix

TIME O(N·M)SPACE O(1)PYTHON · TRAINING PACE · 9 LN

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

TIME O(N·M)SPACE O(1)JAVA · RACE PACE · 14 LN

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

TIME O(N·M)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED