Quick Overview

Find the longest starting string shared by every array element, including inputs with empty strings or no nonempty common prefix.

Find the Shared Starting String

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Other

### Problem Given a nonempty array `words` of strings, return the longest string that occurs at the start of every array element. If the strings have no nonempty common prefix, return `""`. A prefix starts at position `0` and uses consecutive characters. Any array element may itself be empty. Preserve the original `longestCommonPrefix` interface: one array of strings and a string result. ### Examples **Example 1** ```text Input: words = ["interact","internet","internal"] Output: "inter" ``` The first five characters agree. The next position differs between `"interact"` and the other two strings. **Example 2** ```text Input: words = ["sun","moon"] Output: "" ``` The first characters already differ. ### Constraints - There are between `1` and `200` strings. - Every string has length from `0` through `200`. - Nonempty strings contain only lowercase English letters.

Overview: Find the longest starting string shared by every array element, including inputs with empty strings or no nonempty common prefix.

Given a nonempty array `words` of strings, return the longest string that is a prefix of every element of `words`. A prefix starts at position `0` and consists of consecutive characters, so the empty string is a prefix of every string. If the strings share no nonempty common prefix, return the empty string `""`. Any element of `words` may itself be the empty string, in which case the answer is `""`. The answer is unique: it is exactly the longest common prefix, which is never longer than the shortest element. Implement `longestCommonPrefix(words)`, which takes one array of strings and returns a single string. **Example 1** ```text Input: words = ["interact", "internet", "internal"] Output: "inter" ``` The first five characters `i, n, t, e, r` agree in all three strings; at index `5` the first string has `a` while the other two have `n`. **Example 2** ```text Input: words = ["sun", "moon"] Output: "" ``` The first characters already differ, so the only common prefix is the empty string. **Constraints** - `1 <= words.length <= 200` - `0 <= words[i].length <= 200` - Every nonempty `words[i]` contains only lowercase English letters (`a`-`z`).

Constraints

  • 1 <= words.length <= 200
  • 0 <= words[i].length <= 200
  • Every nonempty words[i] consists only of lowercase English letters a-z

Examples

Input: (['interact', 'internet', 'internal'],)

Expected Output: 'inter'

Input: (['sun', 'moon'],)

Expected Output: ''

Hints

  1. The common prefix can never be longer than any single word, so the first word bounds the answer.
  2. Scan character positions from left to right and stop at the first position where some word either ends or has a different character.
  3. An empty string anywhere in the array forces the answer to be empty.

Community answers

Answer by EZ

def find_shared_starting_string(words: list[str]) -> str: """ Approach: horizontal scan with a running prefix. Shrink the prefix against each word; stop early once it becomes empty. Time: O(total characters), Space: O(L) """ if not words: return "" prefix = words[0] def get_prefix(a: str, b: str) -> str: # Advance while characters match; i ends at the first mismatch. i = 0 limit = min(len(a), len(b)) while i < limit and a[i] == b[i]: i += 1 return a[:i] # outside the loop, so it runs after scanning finishes for w in words: if not w.startswith(prefix): prefix = get_prefix(prefix, w) # Only need to check after shrinking: an empty prefix can't grow back. if not prefix: return "" return prefix

Loading coding console...

Show the approach

Approach

The reference uses vertical scanning. It takes the first word as the candidate and walks its character positions from left to right. At each index i it checks every other word: if a word is too short to have an index i, or its character at i differs from the first word's, the common prefix ends just before i and the reference returns the first i characters of the first word. If the scan finishes the whole first word, every word starts with it, so the first word itself is the answer. Because it stops at the first disagreement, it examines at most (length of the common prefix + 1) characters per word, which also handles empty strings and single-word arrays without special cases.

Time complexity:
O(S), where S is the total number of characters across all words (more precisely O(n * (p + 1)) for n words and common-prefix length p)
Space complexity:
O(1) extra space beyond the returned string