#14 Longest Common Prefix

Easysolve on LeetCode ↗

frequently reported atBloomberg Apple Google Amazon Microsoft Adobe

the problem

In plain words

Return the longest string that is a prefix of every string in the array, or "" if there is none.

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

out "fl"

in strs = ["dog","racecar","car"]

out ""

1 ≤ strs.length ≤ 200
0 ≤ strs[i].length ≤ 200
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternCompare at the first difference Trie (prefix tree)

Compare column by column across all strings. The first column where any string differs (or ends) is where the prefix stops.

solutions

From brute force to optimal

Start with the first string as the prefix; chop its end until each next string starts with it.

prefix = strs[0].
For each other string: while it doesn't start with prefix, drop prefix's last char.

timeO(n·m + m²)

n startsWith checks of up to m chars, plus at most m shrinks (each a new substring).

spaceO(m)

The prefix substrings.

javajava.util.*

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        String prefix = strs[0];4        for (int i = 1; i < strs.length; i++) {5            while (!strs[i].startsWith(prefix)) {6                prefix = prefix.substring(0, prefix.length() - 1); // drop the last char7            }8        }9        return prefix;10    }11}

Check character col of every string; stop at the first mismatch or end of a string.

For col in 0..len(first)−1.
If any string is too short or differs at col → return first.substring(0, col).
Return first.

timeO(S)

S = total characters; it stops at the first mismatch, so often far less.

spaceO(1) extra

Only indices (plus the returned substring).

javajava.util.*

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        String first = strs[0];4        for (int col = 0; col < first.length(); col++) {5            char c = first.charAt(col);6            for (int i = 1; i < strs.length; i++) {7                if (col == strs[i].length() || strs[i].charAt(col) != c) {8                    return first.substring(0, col); // first mismatch ends the prefix9                }10            }11        }12        return first;13    }14}

After a lexicographic sort, the first and last strings differ the most; their common prefix is everyone's.

Sort a copy.
Compare sorted[0] and sorted[n−1] char by char.

timeO(m · n log n)

n log n string comparisons, each up to m chars.

spaceO(n)

The sorted copy of references.

javajava.util.*

1class Solution {2    public String longestCommonPrefix(String[] strs) {3        String[] sorted = strs.clone();4        Arrays.sort(sorted);                  // lexicographic order5        String a = sorted[0], b = sorted[sorted.length - 1];6        int i = 0;7        while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;8        return a.substring(0, i);             // the two most different strings decide9    }10}

Insert all strings into a trie (see the Tries chapter); from the root, descend while the node has exactly one child and isn't the end of a word.

Insert every string, tracking childCount and isEnd.
Walk down while childCount == 1 && !isEnd, appending the letter.

timeO(S)

Building the trie touches every character once; the walk is at most the shortest length.

spaceO(S·26)

Up to S trie nodes, each with 26 child slots.

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        int childCount;5        boolean isEnd;6    }7 8    public String longestCommonPrefix(String[] strs) {9        Node root = new Node();10        for (String s : strs) {11            Node cur = root;12            for (char ch : s.toCharArray()) {13                int i = ch - 'a';14                if (cur.children[i] == null) {15                    cur.children[i] = new Node();16                    cur.childCount++;17                }18                cur = cur.children[i];19            }20            cur.isEnd = true;21        }22        // Walk down while the path is a single lane: exactly one child and no word ends here.23        StringBuilder sb = new StringBuilder();24        Node cur = root;25        while (cur.childCount == 1 && !cur.isEnd) {26            int i = 0;27            while (cur.children[i] == null) i++;28            sb.append((char) ('a' + i));29            cur = cur.children[i];30        }31        return sb.toString();32    }33}

in the room

How to say it in the interview

talk track

Present vertical scanning — it naturally stops at the shortest string and the first mismatch.
Mention the sort trick as a neat alternative, but note it's slower.
Offer the trie when asked: "if we receive many queries against the same set, or strings arrive over time, a trie keeps the answer ready."

traps

Calling charAt(col) on a string shorter than col — check the length first.
In the trie walk, ignoring isEnd: with ["ab", "abc"] you'd return "abc".

what they ask next

Follow-ups

Many queries against the same word list?

Build a trie once; the common prefix is the path from the root while nodes have one child and aren't word ends.

Strings arrive one by one and you must report the LCP after each?

Keep the current LCP and shrink it against each new string — or maintain a trie; either is O(length) per new string.

before you submit

Edge cases to test

One string → the whole string.
An empty string anywhere → "".
One string is a prefix of another (["ab", "abc"] → "ab").

practise next