Skip to main content

14. Longest Common Prefix

easy

Find the longest string prefix shared by every word in an array. A friendly warm-up that surfaces vertical-scan thinking and clean early-exit logic.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.

Examples

Example 1

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

Example 2

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

Explanation: There is no common prefix among the input strings.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

What's the maximum possible length of the answer? You can never beat the shortest string.

Hint 2

Try a vertical scan: column by column, check that every string agrees on the same character.

Hint 3

As soon as one string is shorter than the current column or disagrees, return what you've matched so far.

Solution approach

Reveal approach

Vertical scan. For each column index i starting at 0, take c = strs[0][i] (return strs[0] if i reaches its length). Walk through strs[1..], and at any string where i has run past its length or the character at i differs from c, return strs[0].substring(0, i). If you make it past the inner loop, advance i. Time O(S) where S is the total number of characters across all strings — every char is visited at most once. Space O(1) beyond the output.

Complexity

Time
O(S)
Space
O(1)

Related patterns

  • string-matching

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Google

More Strings practice problems

See all Strings problems →