Skip to main content

14. Longest Common Prefix

easyAsked at GoDaddy

Find the longest shared prefix among an array of strings — GoDaddy's domain-autocomplete service uses exactly this vertical scanning approach to build prefix-filtered suggestion lists from millions of registered domain names in real time.

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

Examples

Example 1

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

Example 2

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

Explanation: No common prefix exists among the input strings.

Approaches

1. Horizontal scanning

Start with the first string as the prefix; shrink it character by character until every string starts with it.

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

Tradeoff:

2. Vertical scanning

Compare characters column by column across all strings simultaneously; stop at the first mismatch or end-of-string.

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

Tradeoff:

GoDaddy-specific tips

GoDaddy uses this problem to benchmark string-indexing fundamentals and see whether you reach for indexOf or startsWith without understanding the character-level loop. Vertical scanning is preferred in their codebase because it short-circuits as soon as a column mismatches, which is critical when the prefix diverges early across large domain sets.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →