Skip to main content

16. Longest Common Prefix

easyAsked at Wix

Find the longest string prefix shared by an array of strings — Wix uses this as a proxy for CSS class-name deduplication and URL-path trie reasoning that matters in their routing and SEO infrastructure.

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

Problem

Write a function to find the longest common prefix string among an array of strings. Return an empty string if there is no common prefix.

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"

Explanation: All three strings share the prefix 'fl'; 'flo' is not shared by 'flight'

Example 2

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

Explanation: No common prefix exists

Approaches

1. Horizontal scanning

Start with the first string as the candidate prefix; shorten it until every subsequent string starts with it.

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

Tradeoff:

2. Vertical scanning

Compare column by column — check the i-th character of every string before advancing to i+1. Stops as soon as a mismatch or string end is hit.

Time
O(S) worst case, early exit on first mismatch
Space
O(1)
function longestCommonPrefix(strs) {
  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:

Wix-specific tips

Wix often follows up by asking how you'd extend this to a trie for autocomplete — mention that vertical scanning naturally maps to trie traversal, and you'll signal familiarity with the data structure their search and slug-routing teams rely on.

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 Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →