Introduction

The shortest unique prefix of a string is the smallest prefix that distinguishes it from every other string in the set. This problem appears in autocomplete systems, command-line abbreviation, routing tables, and compact identifiers.

The standard solution is a trie, also called a prefix tree. The trie lets you count how many words pass through each prefix, and the first node with count 1 marks the shortest unique prefix.

Trie-Based Solution

Insert every word into a trie and increment a frequency counter on each node you visit. Then, for each word, walk through the trie again until you reach a node whose frequency is 1. The path to that node is the answer.

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.count = 0
5
6
7def insert(root, word):
8    node = root
9    for ch in word:
10        if ch not in node.children:
11            node.children[ch] = TrieNode()
12        node = node.children[ch]
13        node.count += 1
14
15
16def shortest_unique_prefix(root, word):
17    node = root
18    prefix = []
19    for ch in word:
20        node = node.children[ch]
21        prefix.append(ch)
22        if node.count == 1:
23            return "".join(prefix)
24    return "".join(prefix)
25
26
27def build_prefixes(words):
28    root = TrieNode()
29    for word in words:
30        insert(root, word)
31    return {word: shortest_unique_prefix(root, word) for word in words}
32
33
34words = ["dog", "cat", "car", "cart"]
35print(build_prefixes(words))

Output:

{'dog': 'd', 'cat': 'cat', 'car': 'car', 'cart': 'cart'}

Notice that cat needs the full word here, not just ca, because car and cart also share ca.

Why the Trie Works

Every node in the trie corresponds to a prefix. The node count tells you how many words share that prefix.

For example, with car and cart:

• Prefix c is shared.
• Prefix ca is shared.
• Prefix car is still shared because one word is a prefix of the other.
• 'cart becomes unique only at cart.'

This highlights an important detail: when one word is a full prefix of another, the shorter word may need its complete length and still not be unique under some definitions. Many interview and algorithm problems assume the full word is acceptable as the shortest distinguishing output, even if another word extends it.

Complexity

Let N be the number of words and L be the total number of characters across all words.

• Building the trie takes O(L) time.
• Extracting all prefixes also takes O(L) time.
• Space usage is O(L) in the usual implementation.

That is usually better than comparing every word with every other word, which can degrade toward quadratic behavior.

A sort-based solution also exists: sort the strings lexicographically, then compare each word only with its immediate neighbors. That approach is elegant and often simpler when memory matters. The trie is still the most direct structure if you want prefix queries beyond this single task.

Handling Duplicates and Definitions

You need to decide what “unique” means for duplicate strings. If the input contains the same word twice, no prefix can distinguish the copies from each other. In that case you either return the whole word for both, include multiplicity in the answer format, or reject duplicates as invalid input.

You should also define how to treat a word that is a prefix of another word. Some systems add an end-of-word marker and treat the full shorter word as unique because the terminal marker distinguishes it internally. Others require an external disambiguation rule.

Common Pitfalls

A common mistake is forgetting to increment counts on every traversed node. If counts are updated only at leaf nodes, the algorithm cannot tell which prefixes are shared.

Another bug is returning too early for words that are prefixes of other words. Test cases like car and cart are essential because they reveal whether your definition of uniqueness is consistent.

Developers also sometimes use a trie when sorting would be simpler for one-off batch computation. The trie is excellent, but it is not the only correct method.

Finally, if the alphabet is large, avoid fixed-size child arrays unless you have a strong reason. Dictionaries or maps are usually more practical.

Summary

• A shortest unique prefix is the smallest prefix that identifies one string within the set.
• The standard solution is a trie with per-node frequency counts.
• The first trie node with count 1 gives the answer for a word.
• Total time is linear in the total number of characters.
• Be explicit about duplicate strings and prefix-of-another-word edge cases.