Longest Common Prefix of an Array of Strings

Easy10–15 min

Topics

String

Companies

AmazonMicrosoftGoogleAdobe

Given an array of strings strs, return the longest common prefix shared by every string in the array. If there is no common prefix, return an empty string "". Two natural ways to search for it: vertical scanning checks one character position across every string before moving to the next; horizontal scanning starts with the whole first string as a guess and shrinks it against each remaining string until it fits everywhere. Both do the same character comparisons in the worst case — the difference is just which order you visit them in.

Test Case 1:

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

Output:"fl"

Explanation:"fl" is the longest prefix all three strings start with — "flo" fails since "flight" has 'i' instead of 'o'.

Test Case 2:

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

Output:""

Explanation:The strings don't even share a first character, so there's no common prefix at all.

Test Case 3:

Input:strs = ["single"]

Output:"single"

Explanation:With only one string, its entire length is trivially the common prefix.

Constraints

◆1 ≤ strs.length ≤ 200
◆0 ≤ strs[i].length ≤ 200
◆strs[i] consists of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

strs (comma-separated words) — 1-4 lowercase words

1	class Solution {
2	public String longestCommonPrefix(String[] strs) {
3	if (strs.length == 0) return "";
4	String prefix = strs[0];
5	for (int i = 1; i < strs.length; i++) {
6	while (!strs[i].startsWith(prefix)) {
7	prefix = prefix.substring(0, prefix.length() - 1);
8	if (prefix.isEmpty()) return "";
9	}
10	}
11	return prefix;
12	}
13	}
14

String

Variables

strsLength3

INITIALIZE

strs is not empty. Start with a candidate prefix and shrink it whenever it stops fitting a string.

Step 1 / 13

Approach & Solutions

Brute Force — Vertical Scanning

Brute

Walk character position by character position (0, 1, 2, ...) up to the length of the first string. At each position, check whether every other string agrees on that same character. Stop the moment any string disagrees (or runs out of characters) and return everything matched so far. S is the total number of characters across all strings.

TimeO(S)

SpaceO(1)

Java

Try it out

class Solution {
    public 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];
    }
}

Optimal — Horizontal Scanning

Optimal

Start with the whole first string as a candidate prefix. Compare it against each remaining string in turn — whenever the candidate doesn't fit (the string doesn't start with it), chop one character off the end and try again. By the time every string has been checked, whatever candidate survives is the answer. Same worst-case character comparisons as vertical scanning, but the code reads as "shrink a guess" rather than "scan a grid."