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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Common Prefix and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →