Shortest Unique Prefix for Every Word (Trie)

Problem Statement

Given an array of strings, find the shortest prefix of every word such that the prefix uniquely identifies that word among all other words.

Note: No word is a prefix of another word.

Example 1

Input

arr = {"zebra", "dog", "duck", "dove"}

Output

z dog du dov

Explanation

z uniquely identifies zebra.
dog is needed because do is shared with dove.
du uniquely identifies duck.
dov uniquely identifies dove.

Example 2

Input

arr = {"geeksgeeks", "geeksquiz", "geeksforgeeks"}

Output

geeksg geeksq geeksf

Intuition

A brute-force solution would compare every word with every other word.

For each word:

Check the prefix of length 1.
If it is not unique, check the prefix of length 2.
Continue until a unique prefix is found.

This requires comparing each word with every other word.

Time Complexity

O(N² × L)

Where:

N = Number of words
L = Length of each word

This approach becomes inefficient for large inputs.

Efficient Approach: Trie

A Trie (Prefix Tree) is specially designed to store strings based on their prefixes.

Instead of repeatedly comparing strings, we store all words in a Trie and count how many words pass through each node.

Key Observation

Suppose we insert:

dog
duck
dove

The Trie looks like:

(root)
   |
   d (3)
   |
   o (3)
  / \
 g   v
(1) (1)
 |
 u
(1)

The numbers represent how many words pass through each node.

For dog:

d -> count = 3
o -> count = 3
g -> count = 1

The first node having count = 1 is g.

Therefore:

dog

is the shortest unique prefix.

Algorithm

Step 1

Create a Trie.

Each node stores:

children
count

static class TrieNode{
    TrieNode[] child = new TrieNode[26];
    int count;
}

Step 2

Insert every word.

While inserting:

Increase the count of every node visited.

Example:

Insert:

duck

root
 |
 d(count=1)
 |
 u(count=1)
 |
 c(count=1)
 |
 k(count=1)

Now insert:

dove

root
 |
 d(count=2)
 |
 o(count=1)

Notice:

d.count = 2

because two words start with d.

Step 3

Traverse every word again.

Stop when:

count == 1

because no other word passes through that node.

That prefix is unique.

Dry Run

Input

["zebra","dog","duck","dove"]

After inserting `"zebra"`

root
 |
 z(1)
 |
 e(1)
 |
 b(1)
 |
 r(1)
 |
 a(1)

Insert `"dog"`

root

├── z(1)

└── d(1)
     |
     o(1)
     |
     g(1)

Insert `"duck"`

root

└── d(2)
    |
    o(1)

    u(1)

Now:

d.count = 2

Insert `"dove"`

root

└── d(3)
    |
    o(2)
   / \
  g   v

Final counts:

d = 3

o = 2

g = 1

u = 1

v = 1

Finding Prefixes

Word = `zebra`

z

count = 1

Stop.

Answer:

Word = `dog`

d

count = 3

Continue

o

count = 2

Continue

g

count = 1

Stop

Answer:

dog

Word = `duck`

d

count = 3

Continue

u

count = 1

Stop

Answer:

du

Word = `dove`

d

count = 3

Continue

o

count = 2

Continue

v

count = 1

Stop

Answer:

dov

Final Output

z
dog
du
dov

Understanding the Code

Trie Node

static class TrieNode {
    TrieNode[] child = new TrieNode[26];
    int count = 0;
}

Explanation

Each Trie node contains:

TrieNode[] child = new TrieNode[26];

This stores pointers for:

a
b
c
...
z

For example:

child[0]  -> a

child[1]  -> b

child[25] -> z

The variable:

int count;

stores:

How many words pass through this node.

Creating the Root

TrieNode root = new TrieNode();

Initially:

root

contains no children.

Inserting Words

for(String word : arr){

Insert every word one by one.

The current node starts from the root.

TrieNode curr = root;

Traverse every character.

for(char ch : word.toCharArray()){

Example:

duck

d

u

c

k

Convert the character into an array index.

int idx = ch - 'a';

Examples:

Character	Calculation	Index
'a'	97 - 97	0
'b'	98 - 97	1
'z'	122 - 97	25

Create a node if it does not exist.

if(curr.child[idx]==null)
    curr.child[idx]=new TrieNode();

Move to the next node.

curr=curr.child[idx];

Increase the count.

curr.count++;

Meaning:

One more word passes through this node.

Finding the Prefix

Traverse every word again.

for(String word : arr)

Start from the root.

TrieNode curr = root;

Store the answer.

StringBuilder prefix = new StringBuilder();

Traverse every character.

for(char ch : word.toCharArray())

Move to the next node.

curr = curr.child[idx];

Append the character.

prefix.append(ch);

Check:

if(curr.count==1)
    break;

Once count becomes 1, no other word shares this prefix.

Stop immediately.

Store the answer.

ans.add(prefix.toString());

Complete Code

class Solution {

    static class TrieNode {
        TrieNode[] child = new TrieNode[26];
        int count = 0;
    }

    public ArrayList<String> findPrefixes(ArrayList<String> arr) {

        TrieNode root = new TrieNode();

        // Step 1: Insert all words into the Trie
        for (String word : arr) {
            TrieNode curr = root;

            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';

                if (curr.child[idx] == null) {
                    curr.child[idx] = new TrieNode();
                }

                curr = curr.child[idx];
                curr.count++;
            }
        }

        // Step 2: Find the shortest unique prefix for each word
        ArrayList<String> ans = new ArrayList<>();

        for (String word : arr) {
            TrieNode curr = root;
            StringBuilder prefix = new StringBuilder();

            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';

                curr = curr.child[idx];
                prefix.append(ch);

                if (curr.count == 1)
                    break;
            }

            ans.add(prefix.toString());
        }

        return ans;
    }
}

Complexity Analysis

Operation	Complexity
Insert all words	O(N × L)
Find prefixes	O(N × L)
Total Time	O(N × L)
Auxiliary Space	O(N × L)

Where:

N = Number of words
L = Average length of each word

Why Trie Is the Best Choice

Avoids comparing every word with every other word.
Uses prefix sharing efficiently by storing common prefixes only once.
Each character is processed a constant number of times—once during insertion and once during lookup—resulting in an optimal O(N × L) solution that satisfies the expected constraints.

Summary

A Trie provides an efficient way to find the shortest unique prefix for every word by storing common prefixes and maintaining a count of how many words pass through each node. During insertion, each node records its frequency, and during lookup, the first node with a count of 1 marks the shortest unique prefix. This approach reduces the time complexity from O(N² × L) in the brute-force solution to an optimal O(N × L) while using O(N × L) auxiliary space.

Problem Statement

Example 1

Input

Output

Explanation

Example 2

Input

Output

Intuition

Time Complexity

Efficient Approach: Trie

Key Observation

Algorithm

Step 1

Step 2

Step 3

Dry Run

Input

After inserting "zebra"

Insert "dog"

Insert "duck"

Insert "dove"

Finding Prefixes

Word = zebra

Word = dog

Word = duck

Word = dove

Final Output

Understanding the Code

Trie Node

Explanation

Creating the Root

Inserting Words

Finding the Prefix

Complete Code

Complexity Analysis

Why Trie Is the Best Choice

Summary

After inserting `"zebra"`

Insert `"dog"`

Insert `"duck"`

Insert `"dove"`

Word = `zebra`

Word = `dog`

Word = `duck`

Word = `dove`