Longest start shared by every word

Strings and tries Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
words = ["flower", "flow", "flight"]
lo, hi = min(words), max(words)
i = 0
while i < len(lo) and lo[i] == hi[i]:
    i += 1
print(lo, hi, lo[:i])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A flight flower fl

Right: the smallest and largest words share 'fl', so every word does.

Only the two extreme words need comparing, since everything sorted between them shares at least their common start.

Why not the others?
  • B flow flower flow. flight sorts before flow.
  • C flight flow fl. flower sorts after flow because it is longer with the same start.

30-second answer

Compare column by column: for position i, check that every word has a letter there and that it matches the first word's. Stop at the first mismatch. O(S) time for S total letters in the worst case, O(1) extra memory. Comparing only the smallest and largest word in sorted order also works, since they differ the most.

Practise saying it · 30 s. No recording, just a timer

Explain finding the shared start.

Say your answer out loud, then check which of these points you covered:

  • Column by column
  • Stop at the first mismatch
  • Or compare min and max

Deep dive

Column-by-column stops at the earliest mismatch, which is fast on real data.

min() and max() of the words (no full sort) give the two most different words: compare those two.

A trie gives the answer as the path until the first branching node.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def shared_start(words: list[str]) -> str:
    if not words:
        return ""
    first = words[0]
    for i, ch in enumerate(first):
        for w in words[1:]:
            if i == len(w) or w[i] != ch:  # this column disagrees
                return first[:i]
    return first

Common mistakes

  • Indexing past the end of a shorter word.
  • Comparing only the first two words.

Senior take & follow-ups

Mention the min/max trick as a neat alternative.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why does comparing min and max work?

    Show hint

    Any prefix shared by the alphabetically smallest and largest words is shared by everything between them.

  2. How would a trie answer it?

    Show hint

    Walk from the root while the node has one child and no word ends there.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.