Shortest Unique Prefixes

Tags

Shortest Unique Prefixes

Category

Tries

Difficulty

Hard

Problem Statement

Given an array of strings (all unique), find the shortest prefix for each string such that it uniquely identifies the string among all strings in the array.

Intuition

A trie naturally encodes shared prefixes. When we insert all words into a trie, each node can track how many words pass through it (its frequency count). The shortest unique prefix for a word is the prefix that ends at the first node with a frequency count of 1 — meaning no other word shares that prefix.

Approach

  1. Build a trie, inserting all words. At each node, maintain a count of how many words pass through it.
  2. For each word, traverse the trie character by character:
    • At each node, check if the count is 1.
    • If yes, the prefix up to and including this character is the shortest unique prefix.
    • If no node reaches count 1 (only possible if a word is a prefix of another, but since all words are unique, we eventually reach a count-1 node or the end of the word).
  3. Return the list of shortest unique prefixes.

Pseudocode

class TrieNode:
    children = {}
    count = 0

function buildTrie(words):
    root = new TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = new TrieNode()
            node = node.children[char]
            node.count += 1
    return root

function shortestUniquePrefixes(words):
    root = buildTrie(words)
    result = []

    for word in words:
        node = root
        prefix = ""
        for char in word:
            node = node.children[char]
            prefix += char
            if node.count == 1:
                break
        result.append(prefix)

    return result

Time & Space Complexity

MeasureComplexityJustification
TimeO(N)Where N is the total number of characters across all words; each character is visited once during insertion and once during query
SpaceO(N)Trie storage proportional to total character count

Key Insights

  • The count at each trie node represents how many words share the prefix ending at that node. When the count drops to 1, the prefix is unique.
  • If a word is a prefix of another word (e.g., "app" and "apple"), the unique prefix for the shorter word is the entire word itself, and the longer word's unique prefix extends beyond the shorter word's length.
  • This approach works because all input strings are guaranteed to be unique — otherwise, a count of 1 might never be reached for duplicate words.
  • The same trie structure is useful for autocomplete, spell checking, and IP routing.

Edge Cases

  • Single word: its shortest unique prefix is just its first character (count at root's child is 1).
  • Words with a common long prefix: e.g., "abcx" and "abcy" — the unique prefix for each requires going all the way to the differing character.
  • One word is a prefix of another: e.g., "car" and "card" — "car" itself is its unique prefix; "card" (the full word) is needed for the longer one.
  • All words start with different characters: every unique prefix is just the first character.
  • Empty string in input: its unique prefix is the empty string (if permitted by the problem).

Linked mentions