Problem 3.3 · StringsEasy

Longest Common Prefix

What it teaches: Keep a running answer (the prefix so far) and shrink it as each new word disagrees.

Practise it on judges as “Longest Common Prefix”.

The problem

Given an array of strings strs, return the longest string that is a prefix of all of them. If there is none, return the empty string "".

Example 1

Input: strs = ["flower", "flow", "flight"]
Output: "fl"

Example 2

Input: strs = ["dog", "racecar", "car"]
Output: ""

Constraints

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

Pattern clues in the wording

→ An answer that can only shrink as you see more input
→ Compare everything against one running candidate

These clues point to Running State in One Pass: Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];
        return prefix;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	strs = ["flower","flow","flight"]	"fl"
2	strs = ["dog","racecar","car"]	""
3	strs = ["alone"]	"alone"

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: shrink a running prefix · O(S), where S is the total number of characters 2. Vertical scan: column by column · O(S)

Optimal: shrink a running prefix

Time O(S), where S is the total number of characters Space O(1) extra

Take strs[0] as the prefix. For each other word, while it doesn't start with the prefix, drop the prefix's last character. If the prefix becomes empty, stop early.

Approach 1

class Solution {
    public String longestCommonPrefix(String[] strs) {
        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;
    }
}

Verdict: Simple and fast; each character is removed from the prefix at most once.

Vertical scan: column by column

Time O(S) Space O(1)

Compare character j of every word. The first column where a word ends or a character differs marks the end of the prefix.

▶ Dry run: Comparing column by columnstrs = ["flower", "flow", "flight"]

↑j

column j(list)

fff

Step 1/3Column 0: every word has 'f'.

Approach 2

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

Verdict: Stops as soon as any word disagrees, so it's fast when the prefix is short.

Before you submit

Edge cases and common mistakes

Test these inputs

One string → itself
An empty string in the list → ""
One word is a prefix of another ("ab", "abc")

Mistakes people make

Reading past the end of a shorter word.
Assuming all strings have the same length.

Interview

Follow-up questions

What if you have to answer this for many queries against a fixed word list?

Can sorting help?