Log inSign up
mediumGeeksforGeeksNot Started

Shortest Unique Prefix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of words, find the shortest unique prefix for each word in the given list. Assume that no word is a prefix of another word.

A unique prefix of a word is a prefix that does not match the prefix of any other word in the list.

Example 1 · Example 1: Four words:

Input: words = ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]
Explanation: - "zebra": z is unique (no other word starts with z). Prefix = "z". - "dog": d is shared by dog, duck, dove (count=3). do is shared by dog, dove (count=2). dog is unique (count=1). Prefix = "dog". - "duck": d (count=3), du (count=1). Prefix = "du". - "dove": d (count=3), do (count=2), dov (count=1). Prefix = "dov".

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 100
  • All words consist of lowercase English letters.
  • No word is a prefix of another word.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Augment Trie nodes with visit frequency counters (node.count).
  • Identify uniqueness invariants in prefix trees (node.count == 1).
  • Produce minimal distinguishing identifiers for datasets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding shortest prefix that uniquely identifies each word in a set.
  • Tracking how many words share each prefix.
  • Guaranteed that no word is a prefix of another word.

Algorithmic Decision Tree:

  • Augment TrieNode with integer count = 0.
  • Insert words into Trie, incrementing count++ on every node visited.
  • For each word, walk Trie until reaching a node where count == 1 and return.

Connected Patterns:

Implement TrieReplace WordsLongest Common Prefix

1. All Pairs Prefix Comparison

Intuition

For each word w_i, test prefixes p = w_i[0..k] from length 1 up to w_i.length(). For each prefix, check if any other word w_j (j \neq i) starts with p. The first prefix that is not shared by any other word is the shortest unique prefix.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: For each word w_i in words:
  2. Step 2: Loop prefix length k from 1 to w_i.length():
  3. Step 3: Check if any other word w_j starts with w_i.substr(0, k).
  4. Step 4: If no other word matches, append prefix to result and break.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6class Solution {
7public:
8 vector<string> findPrefixes(string arr[], int n) {
9 vector<string> result;
10 for (int i = 0; i < n; i++) {
11 string w = arr[i];
12 for (size_t k = 1; k <= w.length(); k++) {
13 string pref = w.substr(0, k);
14 bool unique = true;
15 for (int j = 0; j < n; j++) {
16 if (i != j && arr[j].rfind(pref, 0) == 0) {
17 unique = false;
18 break;
19 }
20 }
21 if (unique) {
22 result.push_back(pref);
23 break;
24 }
25 }
26 }
27 return result;
28 }
29};
30
31int main() {
32 Solution sol;
33 string arr[] = {"zebra", "dog", "duck", "dove"};
34 auto res = sol.findPrefixes(arr, 4);
35 for (const string& s : res) cout << s << " ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N^2 * L^2) — Compares all pairs across all prefix lengths.
  • Space complexity: O(N * L) — Stores result array.

Why Brute Force Doesn't Scale:

With 1,000 words of length 100, brute force takes 108 string operations.

Trie with frequency counter processes all words in a single linear pass of 100,000 operations (~5ms).

2. Sorting and Adjacent LCP Comparison

Intuition

In a sorted list of words, a word's longest shared prefix with ANY word is always shared with its immediate predecessor or successor. Sort words with their original indices. Find LCP with neighbor i-1 and i+1. Unique prefix length is max(lcp1, lcp2) + 1.

When to apply: Compact memory alternative avoiding Trie allocation.

Algorithm

  1. Step 1: Tag words with original indices: (word, index).
  2. Step 2: Sort words alphabetically.
  3. Step 3: For each word i: len1 = LCP(i, i-1) (if i > 0), len2 = LCP(i, i+1) (if i < n-1).
  4. Step 4: Unique prefix length = max(len1, len2) + 1.
  5. Step 5: Restore to original indices and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int getLCP(const string& a, const string& b) {
9 int len = 0;
10 int maxLen = min(a.length(), b.length());
11 while (len < maxLen && a[len] == b[len]) len++;
12 return len;
13 }
14
15public:
16 vector<string> findPrefixes(string arr[], int n) {
17 vector<pair<string, int>> sortedArr(n);
18 for (int i = 0; i < n; i++) sortedArr[i] = {arr[i], i};
19 sort(sortedArr.begin(), sortedArr.end());
20
21 vector<string> result(n);
22 for (int i = 0; i < n; i++) {
23 int lcp1 = (i > 0) ? getLCP(sortedArr[i].first, sortedArr[i - 1].first) : 0;
24 int lcp2 = (i < n - 1) ? getLCP(sortedArr[i].first, sortedArr[i + 1].first) : 0;
25 int prefixLen = max(lcp1, lcp2) + 1;
26 result[sortedArr[i].second] = sortedArr[i].first.substr(0, prefixLen);
27 }
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 string arr[] = {"zebra", "dog", "duck", "dove"};
35 auto res = sol.findPrefixes(arr, 4);
36 for (const string& s : res) cout << s << " ";
37 cout << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N * L + N * L) — Sorting takes O(N log N * L). Adjacent LCP comparisons take O(N * L).
  • Space complexity: O(N * L) — Stores sorted tagged word list.

3. Trie with Node Frequency Counter

Intuition

Every node has children[26] and integer count = 0. Insert all words: as each character node is created or traversed, increment node.count++. To find the shortest unique prefix for word W, walk down the Trie from root. At the very first node where curr.count == 1, stop! The prefix accumulated up to this node is guaranteed to be unique and shortest.

When to apply: Standard optimal solution with strictly linear O(Total characters) time.

Algorithm

  1. Step 1: Define TrieNode with children[26] and count = 0.
  2. Step 2: insert(word): walk from root. At each child node, increment child.count++.
  3. Step 3: getPrefix(word): walk characters. Accumulate into prefix. If curr.count == 1, return prefix immediately.
  4. Step 4: Return prefixes for all words in original order.

Interactive Trace for Shortest Unique Prefix

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Insert 'dog' and 'duck'
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'd'
count: 2
char 'o'
count: 1
char 'u'
count: 1

Node order shown; add connections to display explicit tree edges.

shared: d
Check / comparison
Node 'd' count = 2 (not unique)
Decision / next transition
Node 'd' is shared by 2 words.
Why this step matters

Step 1: Insert dog and duck. Root -> d has count = 2. do has count = 1. du has count = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 int count;
9 TrieNode() : count(0) {
10 for (int i = 0; i < 26; i++) children[i] = nullptr;
11 }
12};
13
14class Solution {
15 TrieNode* root;
16
17 void insert(const string& word) {
18 TrieNode* curr = root;
19 for (char c : word) {
20 int idx = c - 'a';
21 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
22 curr = curr->children[idx];
23 curr->count++;
24 }
25 }
26
27 string getUniquePrefix(const string& word) {
28 TrieNode* curr = root;
29 string prefix = "";
30 for (char c : word) {
31 int idx = c - 'a';
32 curr = curr->children[idx];
33 prefix += c;
34 if (curr->count == 1) return prefix;
35 }
36 return prefix;
37 }
38
39public:
40 vector<string> findPrefixes(string arr[], int n) {
41 root = new TrieNode();
42 for (int i = 0; i < n; i++) insert(arr[i]);
43
44 vector<string> result;
45 for (int i = 0; i < n; i++) {
46 result.push_back(getUniquePrefix(arr[i]));
47 }
48 return result;
49 }
50};
51
52int main() {
53 Solution sol;
54 string arr[] = {"zebra", "dog", "duck", "dove"};
55 auto res = sol.findPrefixes(arr, 4);
56 for (const string& s : res) cout << s << " ";
57 cout << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(Total characters) — Insertion visits each character once. Query visits each character once until uniqueness. Total time is linear in sum of word lengths.
  • Space complexity: O(Total characters * 26) — Trie nodes allocate 26 pointers and one integer count each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Compare All Prefixes Against All WordsO(N^2 * L^2)O(L)For each word, test prefixes of length 1, 2, ... Check if prefix is shared by any other word.Comparing all pairs of words for every prefix length.
2.Better — Sort and Compare with NeighborsO(N log N * L + N * L)O(N * L)Sort words alphabetically. The shortest unique prefix for word i depends only on its longest common prefix with word i-1 and word i+1.Restoring order with index tagging.
3.Optimal — Trie with Node Frequency CounterOptimalO(Total Characters)O(Total Characters * 26)Insert all words into Trie with node.count++. Walk each word until node.count == 1.None. Classical textbook algorithm for shortest unique prefix.

Common Pitfalls & Crucial Edge Cases

Incrementing count on the root node instead of child nodes

Root is visited by all words, so its count is always N.

Not stopping immediately when count == 1

Continuing forward yields a valid unique prefix, but NOT the SHORTEST one.

Assuming no word can have full length as prefix

If two words differ only at the last char, full word length is the unique prefix.

Crucial Edge Cases to Validate:

  • Word shares no prefix with any other word ('zebra') — First character z has count=1. Returns single letter z.
  • Words identical except for last character ('cat', 'car') — Traverses up to distinguishing character. Returns cat and car.
  • All words start with same prefix — Traverses past the shared prefix until the first unique character branching occurs.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly define the invariant: node.count == 1 means exactly one word in the entire dictionary branches through this node.
  2. Explain that stopping at the first count == 1 node guarantees minimal prefix length.
  3. Highlight the linear complexity O(Total characters) for both insertion and retrieval.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does node.count == 1 signify in the Shortest Unique Prefix Trie?

2.What is the time complexity of the Trie approach for N words of maximum length L?

Back to DSA Sheet