GeeksforGeeks Medium

Longest Word with All Prefixes

Among a list of words, find the longest word whose every prefix is also a word in the list. Ties are broken alphabetically.

triestring

Open on GeeksforGeeks ↗

02

Intuition

The condition is about every prefix of a word, and a trie is precisely the structure where a word's prefixes are the nodes along its path. Insert everything, flagging each node that terminates a real word. Then a word qualifies if and only if every node on its path carries that flag — one walk per word, no repeated string slicing. Scanning candidates in sorted order makes the tie-break free: the first word to reach a new maximum length is already the alphabetically smallest of that length.

How to spot this pattern

Build a trie of every word, then re-walk each word checking that every node along its path is marked as a word end. That verifies all prefixes exist in one descent instead of doing a separate lookup per prefix. Sorting first makes the lexicographic tiebreak fall out without comparing strings explicitly.

03

Approach

1

Build the trie with end flags

Insert every word; mark the final node of each with an end-of-word flag. Shared prefixes share nodes automatically.

2

Validate by walking

For a candidate word, walk its path and require the end flag at every single node. The first unflagged node disqualifies it immediately.

3

Sort to make ties free

Process candidates alphabetically and keep a strictly-longer rule. The alphabetical winner is then found without an explicit comparison.

04

Solution & live demo

▶1class Solution:
▶2    def longestWord(self, words):
▶3        root = {}
▶4        for w in words:
▶5            node = root
▶6            for ch in w:
▶7                node = node.setdefault(ch, {})
▶8            node["$"] = True
▶9        best = ""
▶10        for w in sorted(words):
▶11            node, ok = root, True
▶12            for ch in w:
▶13                node = node[ch]
▶14                if "$" not in node:
▶15                    ok = False
▶16                    break
▶17            if ok and len(w) > len(best):
▶18                best = w
▶19        return best

05

Common pitfalls

Checking each prefix with a separate lookup

✗ Wrong

if all(w[:i] in word_set for i in range(1, len(w) + 1)):

✓ Right

for ch in w:
    node = node[ch]
    if "$" not in node: ok = False; break

That slices and hashes a new string for every prefix — O(L²) per word. Walking the trie visits each prefix's node exactly once as a by-product of the descent.

Ignoring the lexicographic tiebreak

✗ Wrong

for w in words:
    if ok and len(w) > len(best): best = w

✓ Right

for w in sorted(words):
    ...

When several valid words share the maximum length, the problem asks for the lexicographically smallest. Iterating in sorted order means the first one of that length wins and > never replaces it.

Testing the final node only

✗ Wrong

if "$" in node: ok = True

✓ Right

if "$" not in node:
    ok = False
    break

That only confirms the word itself is present, which is trivially true. The requirement is that every prefix is also a word, so the check belongs at each step of the walk.

06

Edge cases

No word qualifies

Every candidate breaks at some prefix, so the answer is the empty string.

Single-character words

The only prefix is the word itself, so any length-1 word trivially qualifies.

Two valid words of equal length

Sorted order visits the alphabetically smaller first, and the strict length comparison prevents the later one from replacing it.

07

Complexity

Time

O(total characters)

Space

O(total characters)

Each word is walked twice — once to insert, once to validate — plus an O(n log n) sort of the word list.