Autocomplete Payloads & Reverse/Combined Keys

Autocomplete is a prefix query that has to answer fast on every keystroke. Instead of searching below the prefix node each time, you store the answer in the node while building the trie: the top three suggestions, a count, a sum. Querying then costs one step per typed character. The same "change what you store or insert" idea also handles suffix queries and streams.

The idea#

Suppose that after each typed character you must return up to three words with that prefix, in lexicographic order. Searching below the prefix node on every keystroke is slow. Build the answers into the nodes instead.

Sort the words first.
Insert them in that order. At every node on a word's path, append the word to the node's suggestions list if it holds fewer than three.
To answer, walk the typed text one character at a time and read each node's list.

Why it works: words arrive sorted, so the first three to pass through a node are the three smallest with that prefix. No node ever needs sorting. Once a prefix falls off the trie, every longer prefix is missing too, so every remaining answer is an empty list.

Cost#

Most of the work happens once, at build time, and that is the point. Let $N$ be the number of words, $L$ their average length and $M$ the length of the search word.

Step	Time	Why
Sort	$O(N \log N \cdot L)$	$N \log N$ comparisons, each $O(L)$ for strings
Build	$O(N \cdot L)$	one step per character; appending under a cap of 3 is $O(1)$
Query	$O(M)$	one step per typed character; each list holds at most 3
Total	$O(N \cdot L \cdot \log N + M)$	dominated by the sort

The query side is what makes this attractive for a static catalog with frequent searches.

Let the constraints choose#

The trie isn't always the right answer. With about 1,000 products, sorting and then using binary search (or a brute-force scan) is simpler, uses less memory and is fast enough. With about a million products and many queries, scanning becomes too slow, and the trie's $O(1)$ work per keystroke is worth its memory.

How to spot it#

Look for repeated prefix queries that need a small, ready answer.

"Suggest", "autocomplete", "top k with this prefix" after each keystroke.
"Sum of values of keys with this prefix" (store a sum per node).
"Words with this prefix and this suffix", or "does a suffix of the stream match a word": these need a different key, not a different node.

Template#

The words are sorted before insertion, so the capped lists come out already ordered.

node: children = empty map, suggestions = empty list
for each word in sorted(words):        # sorted: first 3 are smallest
    node = root
    for each ch in word:
        move node to its child for ch, creating it if missing
        if len(node.suggestions) < 3:
            append word to node.suggestions
node = root
for each ch in typed text:
    if node exists: node = node's child for ch, or nothing
    record node.suggestions if node exists, else empty list

The no-trie version#

This is the small-input option from "Let the constraints choose". Sorting plus binary search needs no trie. Binary search finds the first word that is at least the prefix. The matches, if any, are the next few entries.

sort words
prefix = ""
for each ch in typed text:
    prefix += ch
    i = first index with words[i] >= prefix     # bisect_left
    record the words among words[i : i + 3] that start with prefix

Beyond the standard trie#

Everything above uses a plain trie with a payload. Two variants go further, and you may hear them named in interviews. A radix (Patricia) trie merges chains of single-child nodes into one edge labeled with the whole substring, which saves memory; it comes up in system design more than in coding rounds. Aho-Corasick adds failure links, pointers that say where to jump after a mismatch (like KMP's table), so that many patterns can be found in one pass over a text. You rarely code it in full; a reversed trie, or a trie plus a BFS queue, is usually enough for stream problems.

Pitfalls#

These mistakes cause the most wrong answers.

Inserting before sorting. Then the first three words to reach a node aren't the smallest, and you'd have to sort every list.
Continuing after a miss. Once a prefix isn't in the trie, every later answer is empty. Stop walking; do not look up later characters from the old node.
Unbounded payloads. Keep the list capped while inserting, or the memory per node grows with the number of words.
Reaching for a trie on small input. With around a thousand words, sort and binary search is simpler and fast enough.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Search Suggestions System

This is the template as written. Sort the products, insert them with a list capped at three per node, then read one list per typed character. After the first miss, append an empty list for every remaining character.

Hint: Map Sum Pairs

The payload is a number, not a list. Store at each node the total value of the keys that pass through it.

Hint: Stream of Characters

After each new letter you must say whether some word ends at the current position. Store every word reversed and keep the stream's recent letters. Walk the trie from the newest letter backward; stop at the first missing child, or succeed at an end marker.

Hint: Prefix and Suffix Search

Change the key, not the node. For every suffix of a word, insert suffix + "{" + word. A query is then one prefix search for suffix + "{" + prefix. The { sorts right after z and never appears in a word; # is also common. Using two tries, one for prefixes and one for reversed suffixes, is the alternative.

Hint: Palindrome Pairs

Reversed keys help here too. Insert every word reversed. A pair works when one word matches the start of the other's reverse and the leftover part is itself a palindrome.

Key takeaways#

Store the answer in the node while building, so each keystroke costs $O(1)$ .
Sorting before insertion makes "first three seen" equal "three smallest".
After a prefix misses, every later answer is empty.
Let input size decide: sort + binary search for small $N$ , a trie for large $N$ with many queries.
Reversed or combined keys turn suffix and stream questions into prefix questions.

Core idea#

Store the answer in each trie node while you build it: the top three suggestions, a count, a sum. A query then costs one step per typed character. Change what you insert to answer suffix and stream queries.

Key points#

Search Suggestions: sort the products first, then insert them in order.
At each node on a product's path, append the product if the list holds fewer than three.
Sorted input makes the first three to pass a node the three smallest. No list needs sorting.
Query: walk the search word and read each node's list.
After a prefix misses, every later answer is an empty list. Stop walking.
Map Sum: store a sum per node.
Stream of Characters: insert words reversed. Walk back from the newest letter.
Prefix and Suffix Search: insert suffix + "{" + word for every suffix. Query suffix + "{" + prefix.

Cost and choice#

Step	Time
Sort	$O(N \log N \cdot L)$
Build	$O(N \cdot L)$
Query	$O(M)$

About 1,000 products: sort plus bisect_left is simpler and fast enough.
About a million products with many queries: the trie is worth its memory.

Template#

for each word in sorted(words):        # sorted: first 3 are smallest
    node = root
    for each ch in word:
        move node to its child for ch, creating it if missing
        if len(node.suggestions) < 3:
            append word to node.suggestions
node = root
for each ch in typed text:
    if node exists: node = node's child for ch, or nothing
    record node.suggestions if node exists, else empty list

Pitfalls#

Inserting before sorting. The first three are then not the smallest.
Continuing after a miss.
Unbounded payloads. Cap the list while you insert.
A trie on small input. Sort and binary search is enough.

Say it in an interview#

"Sort first, so the first three words through a node are the answer for that prefix."
"Reversed or combined keys turn suffix questions into prefix questions."