DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Longest Common Prefix

easyStrings

Problem statement

Given a non-empty list of strings strs, return the longest string that every element of strs starts with. If the strings share no starting characters, return the empty string "".

Examples

Example 1

Input: strs = ["prod-web-01", "prod-web-02", "prod-worker-01"]

Output: "prod-w"

Explanation: All three start with "prod-w". The next character is "e" in two names but "o" in the third.

Example 2

Input: strs = ["staging", "prod"]

Output: ""

Explanation: The first characters already differ.

Hints

Approach

Vertical scanning. Walk the characters of the first string by position. For each position i, check that every other string has a character at i and that it matches. The first failure ends the prefix.

  1. For each index i and character ch of strs[0]:
  2. For every other string s: if i == len(s) or s[i] != ch, return strs[0][:i].
  3. If the loop finishes, the whole first string is the prefix.

Every character is compared at most once, and the scan stops at the shortest string or the first mismatch.

ComplexityTime O(n·m)Space O(1)
Python
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
first = strs[0]
for i, ch in enumerate(first):
for s in strs[1:]:
if i == len(s) or s[i] != ch: # too short, or a different character
return first[:i]
return first

Follow-up questions

  • Find the longest common prefix measured in whole path components, for example for /var/log/app/a.log and /var/log/api/b.log.
  • Many prefix queries arrive against a fixed list of strings. How would a trie help?

Frequently asked questions

n is the number of strings and m is the length of the prefix you end up scanning (at most the length of the shortest string). The optimal version touches each of those n·m characters once.

Yes. After sorting the list, the common prefix of the whole list equals the common prefix of just the first and last strings, because they are the most different. It is neat but costs O(n log n) comparisons, so vertical scanning is usually better.

Hostnames, file paths, S3 keys and metric names are hierarchical, and "what do these names share?" is a real question when grouping hosts, choosing a common log directory, or building a wildcard pattern such as prod-w*.