Problem statement

Write a function to find the longest common prefix amongst an array of strings. If there is no common prefix, return the empty string "".

Example 1

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

Example 2

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix.

Constraints

• 1 <= strs.length <= 15
• 0 <= strs[i].length <= 20
• strs[i] consists of lowercase English letters.

Hints for Longest Common Prefix

1. Hint 1

   The answer can never be longer than the shortest string.

2. Hint 2

   Shrink a candidate prefix until every string starts with it.

How to solve Longest Common Prefix

Compare the strings column by column rather than string by string. Take the first string as the reference, and at each position check that every other string has the same character there. The first disagreement — or the first string that runs out — ends the prefix.

Approach

1. If the list is empty, the answer is the empty string.
2. For each index i in the first string, take its character c.
3. Check every other string: if it is shorter than i + 1, or its character at i differs from c, stop.
4. Return the first string's prefix up to the stopping index; if the loop completes, the whole first string is the prefix.

Why it works

The common prefix can never be longer than the shortest string, and it must agree with the first string at every position — so scanning the first string's characters covers every candidate length in order. Stopping at the earliest disagreement is exactly the definition of the longest common prefix, and the column-wise order means the scan can exit as soon as it fails, often long before reading the whole input.

Complexity

• Time — O(total characters)
• Space — O(1) beyond the output

Pitfalls

• Guard against a string being shorter than the current index before reading it.
• An empty string anywhere in the list forces an empty answer, which the length guard handles.
• No common prefix means the empty string, not a null or sentinel.
• Sorting the array and comparing only the first and last also works, but is O(n log n) for no benefit here.

Reference solution

Python

from typing import List

def longestCommonPrefix(strs: List[str]) -> str:
    p = strs[0]
    for s in strs[1:]:
        while not s.startswith(p):
            p = p[:-1]
            if not p:
                return ""
    return p

Java

public static 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 k = 1; k < strs.length; k++) {
            if (i >= strs[k].length() || strs[k].charAt(i) != c) return first.substring(0, i);
        }
    }
    return first;
}

C++

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string first = strs[0];
    for (int i = 0; i < (int) first.size(); i++) {
        char c = first[i];
        for (int k = 1; k < (int) strs.size(); k++) {
            if (i >= (int) strs[k].size() || strs[k][i] != c) return first.substr(0, i);
        }
    }
    return first;
}

JavaScript

var longestCommonPrefix = function(strs) {
    let p = strs[0];
    for (const s of strs) {
        while (s.indexOf(p) !== 0) {
            p = p.slice(0, -1);
            if (p === "") return "";
        }
    }
    return p;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy