Longest Common Prefix

EasyStrings · Vertical Scanning🧩 String Manipulation LeetCode #14 ↗Updated Oct 30, 2026

Problem

Given an array of strings strs, return the longest string that every element starts with. If the strings do not even share their first character, return the empty string "".

Input["stamp","stack","stair"]Output"sta"

Input["cat","dog"]Output""

Input["abc","ab","abcd"]Output"ab"

1 ≤ strs.length ≤ 200 · 0 ≤ strs[i].length ≤ 200 · lowercase English letters only

Try it yourself

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Read the strings column by column: the prefix grows while every string has the same character at index c, and the first mismatch or the end of the shortest string fixes the answer — no character beyond it is ever needed.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceTry Every Prefix of the First String

Time O(n · m²)Space O(m)

The answer must be a prefix of strs[0] (length m). Try lengths from m down to 0 and return the first candidate that every string startsWith; the empty prefix always qualifies.

Java

public String longestCommonPrefix(String[] strs) {
    String first = strs[0];
    for (int len = first.length(); len > 0; len--) {
        String cand = first.substring(0, len);
        boolean ok = true;
        for (String s : strs) {
            if (!s.startsWith(cand)) { ok = false; break; }
        }
        if (ok) return cand; // longest length that works
    }
    return "";
}

Obviously correct, but re-checks the same leading characters for every length.

BetterHorizontal Scan (Shrink a Running Length)

Time O(S)Space O(1) extra

Keep len = length of the common prefix seen so far, starting with all of strs[0]. Each next string can only shorten it: count how many leading characters it shares with strs[0], capped at len. S is the total number of characters.

Java

public String longestCommonPrefix(String[] strs) {
    String first = strs[0];
    int len = first.length();
    for (int i = 1; i < strs.length && len > 0; i++) {
        String s = strs[i];
        int j = 0;
        while (j < len && j < s.length() && s.charAt(j) == first.charAt(j)) j++;
        len = j; // the prefix can only shrink
    }
    return first.substring(0, len);
}

Linear in the input, but walks each string's overlap even after a later string kills it.

OptimalVertical Scan (Column by Column)

Time O(n · (L+1)) ≤ O(S)Space O(1) extra

Check index c = 0, 1, 2, … across all strings at once. Stop the moment some string is too short or differs from strs[0] at c; the answer is strs[0][0..c). Only the L+1 columns up to the answer length L are ever read.

Java

public String longestCommonPrefix(String[] strs) {
    String first = strs[0];
    for (int c = 0; c < first.length(); c++) {
        char ch = first.charAt(c);
        for (int i = 1; i < strs.length; i++) {
            // string too short or a different character: prefix ends here
            if (c == strs[i].length() || strs[i].charAt(c) != ch) {
                return first.substring(0, c);
            }
        }
    }
    return first; // strs[0] itself is a prefix of every string
}

Dry run["stamp","stack","stair"]

c column changed

c=0
s
c
t

a

m

p

all 's' → go on
c=1
s

t
c
a

m

p

all 't' → go on
c=2
s

t

a
c
m

p

all 'a' → go on
c=3
s

t

a

m
c
p

'c' ≠ 'm' → "sta" ✔

Touches the fewest characters possible and exits on the first bad column.

Pro tip

Sorting the array and comparing only the first and last strings also works, but costs O(S log n) — mention it as an alternative, not the main answer.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Prefix of the First String	`O(n · m²)`	`O(m)`
Better	Horizontal Scan (Shrink a Running Length)	`O(S)`	`O(1) extra`
Optimal	Vertical Scan (Column by Column)	`O(n · (L+1)) ≤ O(S)`	`O(1) extra`

Common pitfalls

Reading strs[i].charAt(c) before checking its length — index out of bounds.
Returning null instead of "" when nothing is shared.
Forgetting a single-string array — the whole string is the answer.

Interview tips

Say out loud that the answer can never be longer than the shortest string.
Compare horizontal vs vertical scanning and why vertical stops sooner.
Mention the trie approach for many repeated prefix queries.

Pattern

Vertical (column-wise) scan → a property that must hold at the same index across many strings.

My notes saved in this browser