Shared Prefix Finder

You're in a phone screen with Adobe when the interviewer asks, "Given an array of strings, find the longest prefix they all share." You know you've seen this one before. It shows up under different names - "Longest Common Prefix" on most platforms, "Shared Prefix Finder" on Firecode - but the core question is always the same. It's a string manipulation problem that looks deceptively simple, yet it tests whether you can think carefully about edge cases and choose the right scanning strategy. Adobe asks it more than almost any other company, and it's a regular at Uber, Google, Meta, and Amazon.

TL;DR

Initialize the prefix as the first string in the array, then iterate through the remaining strings. For each string, trim the prefix from the end one character at a time until it matches the start of that string. If the prefix becomes empty, return "". After processing all strings, whatever remains is the longest common prefix. This runs in O(n * m) time and O(1) space, where n is the number of strings and m is the average string length.

Why This Problem Matters

Finding the longest common prefix is a foundational string problem that appears in dozens of real-world systems. Autocomplete engines use prefix matching to suggest completions as you type. File systems use it to resolve common directory paths. IP routing tables rely on longest prefix matching to forward packets. Understanding how to efficiently compare prefixes across a set of strings is a skill that transfers well beyond the interview room.

Understanding the Problem

Here is the problem statement:

Write a function that identifies the longest common prefix shared by an array of strings. If the strings do not share a common prefix, the function should return an empty string "".

Constraints:

• The number of strings is between 1 and 200
• Each string has a length between 0 and 200
• All strings consist of lowercase English letters only

A few examples to get our bearings:

longestCommonPrefix(["firecode","fireship","firefly"]) => "fire"
longestCommonPrefix(["interview","inter","internal","internet"]) => "inter"
longestCommonPrefix(["flower","flow","flight"]) => "fl"
longestCommonPrefix(["abc","xyz","def"]) => ""

Edge Cases to Consider

1. Single string: The prefix is the string itself
2. All identical strings: The prefix is the full string
3. Empty string in the array: The prefix is always ""
4. No common prefix at all: Return ""
5. Strings of very different lengths: The prefix can't be longer than the shortest string

Solution Approach

There are several ways to find the longest common prefix. The three most common strategies are:

1. Horizontal scanning - Start with one string as the prefix and trim it against each subsequent string
2. Vertical scanning - Compare characters column by column across all strings
3. Trie-based - Build a trie and walk down the single-child path

The horizontal scanning approach is the most intuitive and the one interviewers typically expect first. It's also the approach used in the Firecode solution for this problem.

Horizontal Scanning: The Intuition

Think of it like this: you have a stack of signs at a highway exit, and you want to find the longest shared beginning across all of them. You'd naturally read the first sign, then hold it up against the second sign and cross out any letters from the end that don't match. Then you'd take your shortened sign and compare it against the third, and so on.

That's exactly what horizontal scanning does:

1. Take the first string as your initial prefix
2. Compare the prefix against the second string
3. If the second string doesn't start with the prefix, chop off the last character and try again
4. Repeat until the prefix matches or becomes empty
5. Move on to the next string with the (possibly shorter) prefix
6. After all strings are processed, whatever prefix remains is the answer

Walking Through the Main Example

For ["firecode", "fireship", "firefly"], here is how the algorithm progresses:

The prefix starts as "firecode". It doesn't match the start of "fireship", so we trim one character at a time until we reach "fire", which does match. Then we check "fire" against "firefly" - it matches immediately. The answer is "fire".

Detailed Trimming Process

When we compare "firecode" against "fireship", the inner while loop does the heavy lifting. Here is every step of that trimming:

Each iteration of the while loop checks whether "fireship".indexOf(prefix) == 0. If not, it removes the last character from the prefix and checks again. After four trims, "fire" is found at position 0 in "fireship", and the while loop exits.

Second Example

For ["interview", "inter", "internal", "internet"]:

The prefix "interview" gets trimmed to "inter" when compared against the second string "inter". From that point on, "inter" already matches the start of "internal" and "internet", so no further trimming occurs.

When There Is No Common Prefix

For input like ["flower", "dog", "car"]:

The prefix "flower" gets trimmed character by character against "dog" until it becomes an empty string. At that point the algorithm returns "" immediately without checking the remaining strings.

Empty String Edge Case

If the array contains an empty string like ["prefix", "pre", ""]:

After trimming to "pre" against the second string, the algorithm encounters the empty string "". No prefix can match the start of an empty string (except the empty string itself), so the prefix gets trimmed all the way down to "".

Best Case: Identical Strings

When all strings are the same, like ["same", "same", "same"]:

The prefix never needs trimming. Each comparison finds an immediate match at index 0, so the algorithm breezes through in linear time.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java solution with detailed comments:

public class Solution {
  public String longestCommonPrefix(String[] strs) {
    // Handle empty or null input
    if (strs == null || strs.length == 0) {
      return "";
    }

    // Start with the first string as the initial prefix
    String prefix = strs[0];

    // Compare the prefix against each remaining string
    for (int i = 1; i < strs.length; i++) {
      // Trim the prefix until it matches the start of strs[i]
      while (strs[i].indexOf(prefix) != 0) {
        // Remove the last character
        prefix = prefix.substring(0, prefix.length() - 1);
        // If nothing is left, there is no common prefix
        if (prefix.isEmpty()) {
          return "";
        }
      }
    }

    return prefix;
  }
}

The outer for loop iterates through the strings starting from index 1. For each string, the inner while loop trims the prefix until indexOf(prefix) == 0, meaning the string starts with the prefix. The key check is indexOf(prefix) != 0 rather than indexOf(prefix) == -1, because we need the prefix to appear specifically at the beginning of the string, not just anywhere within it.

Why indexOf == 0?

This is a subtle but important point. strs[i].indexOf(prefix) returns the position where prefix first appears within strs[i]. We specifically need it at position 0 (the start). If we only checked for != -1, a prefix like "fire" would incorrectly match "campfire" since "fire" appears at position 4, not at the start.

Complexity Analysis

Time Complexity: O(n * m)

In the worst case, we compare every character of every string. If there are n strings each of average length m, the total work is proportional to n * m. The best case occurs when the first two strings have no common prefix at all, allowing an early return after trimming one string down to empty.

Space Complexity: O(1)

The algorithm uses only a single prefix variable that stores a substring of the first input string. No additional data structures are allocated. The substring() calls in Java do create new String objects (since Java 7u6), but the prefix only shrinks, so the total auxiliary space never exceeds the length of the first string. In terms of additional data structures, nothing beyond a single string reference is needed.

Alternative Approaches

For a single-query scenario (which is what the interview problem asks), horizontal scanning is the best choice: simple, O(1) space, and straightforward to explain on a whiteboard.

Common Pitfalls

1. Using indexOf == -1 instead of indexOf != 0: This is the most common bug. You need the prefix at position 0, not just present anywhere in the string. "campfire".indexOf("fire") returns 4, not -1, so a check against -1 would incorrectly accept it.

2. Forgetting the empty string case: If any string in the array is "", the answer is always "". The algorithm handles this naturally through the trimming loop, but it's worth mentioning explicitly in your interview.

3. Not handling single-element arrays: With only one string, the answer is that string. The outer loop simply never executes, and the prefix (initialized to strs[0]) is returned as-is.

4. Off-by-one in substring: When trimming, prefix.substring(0, prefix.length() - 1) correctly removes the last character. Using prefix.length() without the - 1 would leave the prefix unchanged, creating an infinite loop.

Pro tip: Trace through your solution with at least three inputs during the interview: a normal case like ["fire", "firm", "first"], a no-match case like ["abc", "xyz"], and an edge case like [""] or ["a"]. This catches most bugs before the interviewer spots them.

Interview Tips

When this problem comes up in an interview:

1. Clarify the constraints: Ask about empty arrays, empty strings within the array, and whether the answer should be case-sensitive. For this problem, all strings are lowercase, but asking shows thoroughness.

2. Start with horizontal scanning: It's the most natural approach and easy to code correctly. Mention that vertical scanning and trie-based approaches exist, but implement horizontal scanning first.

3. Explain the indexOf == 0 check: Interviewers appreciate when you proactively explain why you check for position 0 rather than just checking if the prefix exists anywhere.

4. Discuss follow-ups if time allows: If the interviewer asks how you'd handle millions of strings or repeated queries, the trie approach becomes relevant. For sorted input, you only need to compare the first and last strings.

5. Watch for the sorted shortcut: If the strings are sorted lexicographically, the longest common prefix of the entire array equals the common prefix of just the first and last strings. This is a nice optimization to mention.

Key Takeaways

• Horizontal scanning initializes the prefix with the first string and trims it against each subsequent string, achieving O(n * m) time and O(1) space.
• The critical check is indexOf(prefix) != 0, not indexOf(prefix) == -1. The prefix must appear at the start of each string, not just anywhere within it.
• Early termination happens naturally: if the prefix becomes empty while processing any string, the algorithm returns "" without checking the rest.
• For sorted input, comparing only the first and last strings gives the answer. This is a strong follow-up point in interviews.
• The trie approach trades O(n * m) extra space for the ability to answer many prefix queries efficiently, making it worthwhile in autocomplete and search suggestion systems.

Related Problems

Once you're comfortable with this problem, these are natural next steps:

• Implement a Trie - Build the data structure that powers prefix lookups at scale
• Word Search - Find words in a grid using prefix-based pruning
• Autocomplete System - Combine prefix matching with frequency ranking

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. String manipulation is one of those categories where consistent practice makes a real difference, and getting reps on prefix problems builds the intuition you need for trie-based questions later on.

Solutions in Other Languages

Python

class Solution:
    def longest_common_prefix(self, strs):
        if not strs:
            return ""

        prefix = strs[0]

        for string in strs[1:]:
            while not string.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""

        return prefix

Python's startswith method reads more naturally than indexOf == 0. The slice prefix[:-1] removes the last character. The logic is identical to the Java version.

JavaScript

function longestCommonPrefix(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.substring(0, prefix.length - 1);
      if (!prefix) return "";
    }
  }
  return prefix;
}

TypeScript

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return "";

  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (!prefix) return "";
    }
  }
  return prefix;
}

C++

#include <vector>
#include <string>

class Solution {
public:
  std::string longestCommonPrefix(std::vector<std::string> &strs) {
    if (strs.empty()) return "";

    std::string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); ++i) {
      while (strs[i].find(prefix) != 0) {
        prefix = prefix.substr(0, prefix.length() - 1);
        if (prefix.empty()) return "";
      }
    }
    return prefix;
  }
};

C++ uses std::string::find which returns the position of the first occurrence, similar to Java's indexOf. The check != 0 serves the same purpose.

Go

package solution

func LongestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    prefix := strs[0]
    for i := 1; i < len(strs); i++ {
        for len(strs[i]) < len(prefix) || strs[i][:len(prefix)] != prefix {
            prefix = prefix[:len(prefix)-1]
            if prefix == "" {
                return ""
            }
        }
    }
    return prefix
}

Go doesn't have a built-in indexOf or startsWith, so the inner loop condition checks two things: whether the current string is shorter than the prefix, and whether the current string's prefix-length substring matches. This avoids an index-out-of-bounds panic on the slice operation.

Scala

class Solution {
  def longestCommonPrefix(strs: Array[String]): String = {
    if (strs.isEmpty) return ""

    var prefix = strs(0)

    for (i <- 1 until strs.length) {
      while (strs(i).indexOf(prefix) != 0) {
        prefix = prefix.substring(0, prefix.length - 1)
        if (prefix.isEmpty) return ""
      }
    }
    prefix
  }
}

Kotlin

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) {
            return ""
        }

        var prefix = strs[0]
        for (i in 1 until strs.size) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.dropLast(1)
                if (prefix.isEmpty()) {
                    return ""
                }
            }
        }
        return prefix
    }
}

Kotlin's startsWith and dropLast make the code particularly readable. dropLast(1) returns a new string with the last character removed.

Swift

import Foundation

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        if strs.isEmpty {
            return ""
        }

        var prefix = strs[0]
        for i in 1..<strs.count {
            while !strs[i].hasPrefix(prefix) {
                prefix = String(prefix.dropLast())
                if prefix.isEmpty {
                    return ""
                }
            }
        }
        return prefix
    }
}

Swift uses hasPrefix for the prefix check and dropLast() to trim one character. The String() wrapper is needed because dropLast() returns a Substring, not a String.

Ruby

class Solution
  def longest_common_prefix(strs)
    return "" if strs.nil? || strs.empty?

    prefix = strs[0]
    strs[1..].each do |str|
      while !str.start_with?(prefix)
        prefix = prefix[0...-1]
        return "" if prefix.empty?
      end
    end
    prefix
  end
end

Ruby's start_with? method and the range slice [0...-1] (exclusive end) handle the trimming naturally.

Rust

pub fn longest_common_prefix(strs: Vec<String>) -> String {
    if strs.is_empty() {
        return String::new();
    }

    let mut prefix = strs[0].clone();
    for i in 1..strs.len() {
        while !strs[i].starts_with(&prefix) {
            prefix.pop();
            if prefix.is_empty() {
                return String::new();
            }
        }
    }
    prefix
}

Rust's pop() method removes the last character from a String in place, which is more efficient than creating a new substring each time.

C#

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs == null || strs.Length == 0) {
            return "";
        }

        var prefix = strs[0];
        for (int i = 1; i < strs.Length; i++) {
            while (strs[i].IndexOf(prefix) != 0) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if (prefix.Length == 0) {
                    return "";
                }
            }
        }
        return prefix;
    }
}

Dart

class Solution {
  String longestCommonPrefix(List<String> strs) {
    if (strs.isEmpty) {
      return "";
    }

    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
      while (!strs[i].startsWith(prefix)) {
        prefix = prefix.substring(0, prefix.length - 1);
        if (prefix.isEmpty) {
          return "";
        }
      }
    }
    return prefix;
  }
}

PHP

class Solution {
    public function longestCommonPrefix(array $strs): string {
        if (empty($strs)) {
            return "";
        }

        $prefix = $strs[0];
        for ($i = 1; $i < count($strs); $i++) {
            while (strpos($strs[$i], $prefix) !== 0) {
                $prefix = substr($prefix, 0, strlen($prefix) - 1);
                if ($prefix === "") {
                    return "";
                }
            }
        }
        return $prefix;
    }
}

PHP uses strpos to find the position of the prefix. Note the strict comparison !== 0 rather than != 0, because strpos returns false when the substring is not found, and in PHP false == 0 is true. Using !== avoids that trap.