Longest Common Prefix

EasystringsString column scanstringseasyprefix

Maintained by Vikas Dulgunde, software engineer

You are handed an array of strings and asked for the longest run of characters that appears at the very start of all of them. The match has to begin at index 0 and stay unbroken: as soon as one string disagrees with the others at some position, the common prefix stops there.

Think of it as lining the words up vertically and reading down each column. While every word has the same letter in a column, that letter belongs to the prefix. The first column where any two words differ, or where any word has already run out of characters, marks the end.

If the array holds a single string, that whole string is the answer, since it trivially agrees with itself. If any string is empty, or the very first characters already disagree, the answer is the empty string.

Examples

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

Output: "fl"

All three begin with 'f' then 'l'. At the third position 'o', 'o', and 'i' disagree, so the shared prefix is "fl".

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

Output: ""

The first characters are 'd', 'r', and 'c', which already differ, so there is no common prefix at all.

Input: ["interview", "inter", "internal"]

Output: "inter"

Every string shares "inter". The word "inter" ends right there, which caps the prefix at five characters even though the others continue.

Constraints

1 <= strs.length <= 200
0 <= strs[i].length <= 200
Each strs[i] contains only lowercase English letters
An empty string anywhere in the array forces the result to be ""

Visible test cases

longestCommonPrefix(["flower","flow","flight"]) == "fl"
longestCommonPrefix(["dog","racecar","car"]) == ""
longestCommonPrefix(["interview","inter","internal"]) == "inter"
longestCommonPrefix(["abc"]) == "abc"
longestCommonPrefix(["abc","abc","abc"]) == "abc"
longestCommonPrefix(["","abc"]) == ""

Hints

Hint 1

The answer can never be longer than the shortest string in the array, and it can never be longer than the first string either.

Hint 2

Try treating the first string as a candidate prefix, then shrink it as you compare it against each remaining string.

Hint 3

You can stop early the moment the candidate prefix becomes empty, since nothing later can revive it.

Loading the editor...

Approaches

Vertical column scan

Time O(n * m) where n is the number of strings and m is the length of the shortest string · Space O(1) beyond the returned string

Walk character positions left to right across all strings at once. The first position where a string ends or a character disagrees is where the prefix stops.

Take the first string as the reference for which characters to check.
For each index i in the reference string, read the character at i.
Compare that character against the character at index i in every other string.
If any string is shorter than i+1, or its character differs, return the reference substring up to i.
If you exhaust the reference string without a mismatch, the whole reference string is the prefix.

Horizontal shrink

Time O(S) where S is the total number of characters across all strings · Space O(1) beyond the returned string

Start with the first string as the full candidate prefix, then trim it against each next string until it fits all of them.

Set prefix to the first string.
For each remaining string, advance a pointer while it matches prefix character by character within both lengths.
Cut prefix down to the matched length.
If prefix ever becomes empty, return "" immediately since no shorter prefix exists.
Return prefix after all strings have been processed.

Common mistakes

Forgetting that an empty string in the array immediately forces the result to "", because nothing can be a prefix of "".
Indexing past the end of a shorter string while comparing; you must check the current length against the index before reading a character.
Returning the first string unchanged when only one string is given is correct, but special-casing it wrongly (for example returning "") is a common slip.
Comparing only the first and last sorted strings without sorting first, or assuming lexical order implies prefix order incorrectly.

Follow-up variations

How would you find the longest common suffix instead of the prefix?
If you had to answer many prefix queries against a fixed set of strings, would a trie change your approach?
Can you solve it with a binary search on the prefix length, and what is its time complexity?
How does the solution change if characters are full Unicode code points rather than single lowercase letters?

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

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

Output: "fl"

All three begin with 'f' then 'l'. At the third position 'o', 'o', and 'i' disagree, so the shared prefix is "fl".

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

Output: ""

The first characters are 'd', 'r', and 'c', which already differ, so there is no common prefix at all.

Input: ["interview", "inter", "internal"]

Output: "inter"

Every string shares "inter". The word "inter" ends right there, which caps the prefix at five characters even though the others continue.

Hints

Hint 1

The answer can never be longer than the shortest string in the array, and it can never be longer than the first string either.

Hint 2

Try treating the first string as a candidate prefix, then shrink it as you compare it against each remaining string.

Hint 3

You can stop early the moment the candidate prefix becomes empty, since nothing later can revive it.

Approaches

Vertical column scan

Time O(n * m) where n is the number of strings and m is the length of the shortest string · Space O(1) beyond the returned string

Walk character positions left to right across all strings at once. The first position where a string ends or a character disagrees is where the prefix stops.

Take the first string as the reference for which characters to check.
For each index i in the reference string, read the character at i.
Compare that character against the character at index i in every other string.
If any string is shorter than i+1, or its character differs, return the reference substring up to i.
If you exhaust the reference string without a mismatch, the whole reference string is the prefix.

Horizontal shrink

Time O(S) where S is the total number of characters across all strings · Space O(1) beyond the returned string

Start with the first string as the full candidate prefix, then trim it against each next string until it fits all of them.

Set prefix to the first string.
For each remaining string, advance a pointer while it matches prefix character by character within both lengths.
Cut prefix down to the matched length.
If prefix ever becomes empty, return "" immediately since no shorter prefix exists.
Return prefix after all strings have been processed.

Common mistakes

Forgetting that an empty string in the array immediately forces the result to "", because nothing can be a prefix of "".

Indexing past the end of a shorter string while comparing; you must check the current length against the index before reading a character.

Returning the first string unchanged when only one string is given is correct, but special-casing it wrongly (for example returning "") is a common slip.

Comparing only the first and last sorted strings without sorting first, or assuming lexical order implies prefix order incorrectly.

Follow-up variations

How would you find the longest common suffix instead of the prefix?

If you had to answer many prefix queries against a fixed set of strings, would a trie change your approach?

Can you solve it with a binary search on the prefix length, and what is its time complexity?

How does the solution change if characters are full Unicode code points rather than single lowercase letters?

Longest Common Prefix

Examples

Constraints

Hints

Approaches

Vertical column scan

Horizontal shrink

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Longest Common Prefix

Examples

Constraints

Hints

Approaches

Vertical column scan

Horizontal shrink

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep