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

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:

This requires comparing each word with every other word.

Time Complexity

O(N² × L)

Where:

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:

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

Step 2

Insert every word.

While inserting:

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:

z

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:

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:

CharacterCalculationIndex
'a'97 - 970
'b'98 - 971
'z'122 - 9725

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

OperationComplexity
Insert all wordsO(N × L)
Find prefixesO(N × L)
Total TimeO(N × L)
Auxiliary SpaceO(N × L)

Where:

Why Trie Is the Best Choice

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.