Skip to main content

14. Longest Common Prefix

easyAsked at Bloomberg

Find the longest common prefix shared by an array of strings. Bloomberg uses this as a string-iteration test — they want clean code that handles the empty-input edge and discusses vertical vs horizontal scan tradeoffs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg phone-screen reports list Longest Common Prefix among the recurring string warm-ups.
  • Blind (2025-12)— Bloomberg SWE intern reports note this as a common Round 1 question.

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.

Approaches

1. Vertical scan (column-by-column)

Walk index 0, 1, 2, ... For each column, check all strings have the same char. Stop on mismatch or end.

Time
O(S)
Space
O(1)
function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  for (let i = 0; i < strs[0].length; i++) {
    const ch = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i === strs[j].length || strs[j][i] !== ch) {
        return strs[0].slice(0, i);
      }
    }
  }
  return strs[0];
}

Tradeoff: Best when the answer is short relative to total input size — we exit early. S = total chars across all strings.

2. Horizontal scan (reduce by pairwise prefix)

Start with strs[0] as the prefix. For each next string, shrink prefix until it's a prefix of that string.

Time
O(S)
Space
O(1)
function longestCommonPrefixHorizontal(strs) {
  if (!strs.length) return '';
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, prefix.length - 1);
      if (!prefix) return '';
    }
  }
  return prefix;
}

Tradeoff: Same worst case but slower in practice on dissimilar inputs because prefix shrinks one char at a time. Bloomberg interviewers want you to know both versions and explain the difference.

Bloomberg-specific tips

Bloomberg interviewers want both the empty-input check and a discussion of WHICH scan you picked. State 'I'll do a vertical scan so I can short-circuit at the first mismatch column' before coding. This frames the problem in terms of the input shape.

Common mistakes

  • Forgetting strs.length === 0 — many candidates assume at least one input.
  • Not checking that subsequent strings can be shorter than strs[0] — going past their end.
  • Returning the wrong slice on early exit (off-by-one).

Follow-up questions

An interviewer at Bloomberg may pivot to one of these next:

  • Longest Common Suffix — reverse all strings and reuse this.
  • Longest Common Subsequence (LC 1143) — 2D DP, very different shape.
  • Group Anagrams (LC 49) — different problem, often paired with this one in the same hour.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Vertical or horizontal — which to prefer?

Vertical is usually faster in practice. Both worst-case O(S). On highly-similar prefixes, horizontal works fine; on dissimilar inputs, vertical short-circuits faster.

Does sorting first help?

Yes — sort lexicographically and compare only the first and last strings. O(S log n) but uses just one comparison instead of n. Useful trick to mention.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Longest Common Prefix and other Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →