Skip to main content
CodePeetCodePeet
CodePeet 250

Longest Common Prefix

EASYProblemSolveExternal Links

Description

Given an array of strings, write a function that finds the longest common prefix shared by all the strings in the array.

A prefix of a string is any leading portion of that string. For example, the prefixes of "flower" are "", "f", "fl", "flo", "flow", "flowe", and "flower". The longest common prefix is the longest string that appears as a prefix of every single string in the array.

If no common prefix exists (i.e., the strings do not all share the same starting character), return an empty string "".

Examples

Example 1

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

Output: "fl"

Explanation: All three strings begin with 'f' and then 'l'. At position 2, "flower" and "flow" have 'o' but "flight" has 'i' — a mismatch. So the longest common prefix is "fl", the two characters that all strings share at their beginning.

Example 2

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

Output: ""

Explanation: The very first character of "dog" is 'd', while the first character of "racecar" is 'r'. Since they differ at position 0, there is no common prefix at all. We return an empty string.

Example 3

Input: strs = ["interspecies", "interstellar", "interstate"]

Output: "inters"

Explanation: All three strings share the prefix "inters" (6 characters). At position 6, we have 'p' (from "interspecies"), 't' (from "interstellar"), and 't' (from "interstate") — not all the same. The longest common prefix is "inters".

Constraints

  • 1 ≤ strs.length ≤ 200
  • 0 ≤ strs[i].length ≤ 200
  • strs[i] consists of only lowercase English letters (if non-empty)

Editorial

Brute Force

Intuition

The most straightforward approach is called horizontal scanning. The idea is simple: start by assuming the entire first string is the common prefix, then compare it with each subsequent string and shrink the prefix whenever it does not match.

Imagine you have a group of friends and you want to find the longest name prefix they all share. You write down the first friend's full name as your "candidate prefix." Then you check the second friend's name — if it does not start with your candidate, you chop off the last character and check again, repeating until the candidate is a prefix of the second name (or becomes empty). You then take this shortened candidate and repeat the process with the third friend's name, and so on.

By the time you have checked all names, whatever remains of the candidate is the longest prefix shared by everyone.

Step-by-Step Explanation

Let's trace through with strs = ["flower", "flow", "flight"]:

Step 1: Initialize the prefix as the entire first string.

  • prefix = "flower"

Step 2: Compare prefix with strs[1] = "flow".

  • Does "flow" start with "flower"? No ("flow" is shorter than "flower").
  • Shorten prefix: remove last character → prefix = "flowe"

Step 3: Does "flow" start with "flowe"? No.

  • Shorten: prefix = "flow"

Step 4: Does "flow" start with "flow"? Yes!

  • prefix stays "flow". Move to the next string.

Step 5: Compare prefix with strs[2] = "flight".

  • Does "flight" start with "flow"? No.
  • Shorten: prefix = "flo"

Step 6: Does "flight" start with "flo"? No.

  • Shorten: prefix = "fl"

Step 7: Does "flight" start with "fl"? Yes!

  • prefix stays "fl". No more strings to check.

Result: prefix = "fl"

Horizontal Scanning — Shrinking the Prefix — Watch how we start with the full first string as the prefix candidate and progressively shorten it each time it fails to match the beginning of the next string.

Algorithm

  1. If the array is empty, return ""
  2. Set prefix = strs[0] (the entire first string)
  3. For each string s in strs[1:]:
    • While s does not start with prefix:
      • Remove the last character from prefix
      • If prefix becomes empty, return ""
  4. Return prefix

Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string prefix = strs[0];
        for (int i = 1; i < strs.size(); i++) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.size() - 1);
                if (prefix.empty()) return "";
            }
        }
        return prefix;
    }
};
class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""
        prefix = strs[0]
        for s in strs[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

Complexity Analysis

Time Complexity: O(S) where S is the sum of all characters across all strings.

In the worst case (all strings are identical), we compare every character of every string against the prefix. The startsWith check in each trimming iteration scans up to the prefix length. Across all strings and all trimming steps, the total character comparisons are bounded by S.

However, this approach can be inefficient in practice. Consider strs = ["abcdefghij", "a"]. We start with prefix = "abcdefghij" (10 chars) and must trim it 9 times, each time calling startsWith (which scans the prefix). That's roughly 10 + 9 + 8 + ... + 1 = 55 character comparisons, whereas a smarter approach would detect the mismatch at position 1 immediately.

Space Complexity: O(m) where m is the length of the first string.

We store the prefix string, which starts as a copy of strs[0] and only shrinks. In the worst case, we store the full first string.

Why This Approach Is Not Efficient

The horizontal scanning approach has a subtle inefficiency: it repeatedly calls startsWith (or indexOf) with gradually shorter prefixes against the same string. Each call rescans from the beginning of the string.

For example, if the prefix is "abcdefghij" and the current string is "abcx", the approach:

  1. Checks if "abcx" starts with "abcdefghij" — scans 4 characters, fails at position 3
  2. Trims to "abcdefghi" — scans 4 characters again, same failure
  3. Trims to "abcdefgh" — scans 4 characters again
  4. ...continues 6 more times before reaching "abc"

Each trim only removes one character, so we redundantly re-check the matching portion multiple times. A smarter approach would scan character positions one at a time across all strings simultaneously, stopping at the first position where any string disagrees. This way, we never re-examine characters we have already confirmed as matching.

Optimal Approach - Vertical Scanning

Intuition

Instead of taking the first string as a prefix and shrinking it, we can think of the problem differently: imagine stacking all the strings on top of each other and reading column by column from left to right.

f l o w e r
f l o w
f l i g h t

Column 0: all 'f' — match!
Column 1: all 'l' — match!
Column 2: 'o', 'o', 'i' — mismatch at "flight"!

The moment we find a column where not all characters agree (or a string is too short to have a character at that column), we stop. Everything to the left of that column is the longest common prefix.

This is called vertical scanning because we scan vertically down each column across all strings, rather than horizontally through one string at a time. The advantage is that we examine each character position exactly once across all strings. We never backtrack or re-examine characters.

Step-by-Step Explanation

Let's trace through with strs = ["flower", "flow", "flight"]:

Step 1: Use strs[0] = "flower" as the reference. We will check each character position i from 0 to 5.

Step 2: Column i=0. Reference character = 'f'.

  • strs[1][0] = 'f' → matches
  • strs[2][0] = 'f' → matches
  • All match! Continue to next column.

Step 3: Column i=1. Reference character = 'l'.

  • strs[1][1] = 'l' → matches
  • strs[2][1] = 'l' → matches
  • All match! Continue.

Step 4: Column i=2. Reference character = 'o'.

  • strs[1][2] = 'o' → matches
  • strs[2][2] = 'i' → MISMATCH!
  • Stop immediately. Return strs[0][0..1] = "fl".

Result: "fl"

Notice we only examined 8 characters total (3 strings × ~2-3 positions each) before finding the mismatch, whereas horizontal scanning performed many more redundant comparisons.

Vertical Scanning — Column-by-Column Comparison — Watch how we scan each character position across all strings simultaneously. The moment any string disagrees, we stop and have our answer.

Algorithm

  1. If the array is empty, return ""
  2. For each character position i from 0 to len(strs[0]) - 1:
    • Let c = strs[0][i] (the character at position i in the reference string)
    • For each string s in strs[1:]:
      • If i >= len(s) (string s is too short), return strs[0][0..i-1]
      • If s[i] != c (character mismatch), return strs[0][0..i-1]
  3. If we finish without returning early, return strs[0] (the entire first string is the common prefix)

Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int i = 0; i < strs[0].size(); i++) {
            char c = strs[0][i];
            for (int j = 1; j < strs.size(); j++) {
                if (i >= strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};
class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""
        for i in range(len(strs[0])):
            c = strs[0][i]
            for s in strs[1:]:
                if i >= len(s) or s[i] != c:
                    return strs[0][:i]
        return strs[0]
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || 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];
    }
}

Complexity Analysis

Time Complexity: O(S) where S is the sum of all characters in all strings.

In the worst case (all strings are identical), we examine every character of every string exactly once. More precisely, if there are n strings and the common prefix has length p, we perform p × n character comparisons. In the best case (no common prefix at all), we check only n characters (column 0) before stopping. The vertical scanning approach is optimal because it stops at the earliest possible position — the first column where any string disagrees.

Space Complexity: O(1)

We only use a few variables: the column index i, the reference character c, and the inner loop index. No additional data structures are allocated. The returned substring is part of the output, not auxiliary space.