Shortest Unique Prefix of Every Word

Given a list of lowercase words, find for each word the shortest prefix that identifies it uniquely: no other word in the list starts with that prefix. Assume no word is a prefix of another.

Example

Text

Input:  ["zebra", "dog", "duck", "dove"]
Output: ["z", "dog", "du", "dov"]

"d" is shared by three words and "do" by two, so "dog" needs three letters. "du" is enough for "duck".

Brute force: test each prefix against every other word

For each word, try prefixes of length 1, 2, ... and stop at the first one that no other word starts with. If no prefix qualifies, the answer is the whole word.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<String> shortestUniquePrefixes(String[] words) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int len = word.length(); // default: the whole word
            for (int l = 1; l <= word.length(); l++) {
                String prefix = word.substring(0, l);
                boolean unique = true;
                for (int j = 0; j < words.length; j++) {
                    if (j != i && words[j].startsWith(prefix)) {
                        unique = false;
                        break;
                    }
                }
                if (unique) {
                    len = l;
                    break;
                }
            }
            result.add(word.substring(0, len));
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(shortestUniquePrefixes(new String[] {"zebra", "dog", "duck", "dove"}));
    }
}

Output

[z, dog, du, dov]

Time: O(n² · L²) for n words of length up to L: up to L prefixes per word, each compared with every other word in O(L). Space: O(L) besides the output, for the short-lived substring copies.

Optimal: a trie with pass-through counts

Insert every word into a trie, and store in each node how many words pass through it. A prefix is unique exactly when its node's count is 1. For each word, walk down the trie and stop at the first node with count 1.

graph TB
    root(("root")) -->|z| z["z: 1"]
    root -->|d| d["d: 3"]
    d -->|o| do["do: 2"]
    d -->|u| du["du: 1"]
    do -->|g| dog["dog: 1"]
    do -->|v| dov["dov: 1"]

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int count; // number of words whose path goes through this node
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
            node.count++;
        }
    }

    static int uniquePrefixLen(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            node = node.children[word.charAt(i) - 'a']; // exists: the word was inserted
            if (node.count == 1) {
                return i + 1;
            }
        }
        return word.length();
    }

    static List<String> shortestUniquePrefixes(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            insert(root, word);
        }
        List<String> result = new ArrayList<>();
        for (String word : words) {
            result.add(word.substring(0, uniquePrefixLen(root, word)));
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(shortestUniquePrefixes(new String[] {"zebra", "dog", "duck", "dove"}));
        System.out.println(shortestUniquePrefixes(new String[] {"apple", "banana", "apricot"}));
    }
}

Output

[z, dog, du, dov]
[app, b, apr]

Time: O(S), where S is the total number of characters: every word is inserted once and walked once. Space: O(S) for the trie.

The root's count isn't updated, because the empty prefix is never an answer.

Edge cases

A single word: its first letter.
A word that is a prefix of another ("do" and "dog"): "do" has no unique prefix at all. The code returns the whole word in that case; ask the interviewer what they expect.
Duplicate words: have no unique prefix either, and also return the whole word.