Shortest Unique Prefix for Every Word

Problem Overview

The shortest unique prefix of a word is the shortest string that starts that word and does not start any other word.

Intuition

The shortest unique prefix of a word is the shortest string that starts that word and does not start any other word. Counting how often each prefix appears across the whole dictionary answers that immediately: walk each word left to right and stop at the first prefix whose global count is 1.

Algorithm

1First pass: for every word, for every prefix, pack characters into a rolling integer key with encode(prev, ch) = (prev << 5) + ch and increment prefixCount[key].
2Second pass: for each word, rebuild the same keys while appending characters to a StringBuilder.
3Stop when prefixCount[key] == 1 (unique) or when the last character is reached, then add that prefix to the result.
4Return the list of prefixes in the same order as the input words.

Example Walkthrough

Input: arr = ["zebra", "dog", "duck", "dove"]

1. Shared prefixes: "d" appears in dog/duck/dove (count 3); "do" appears in dog/dove (count 2); "du" only in duck (count 1).
2. zebra → "z" is unique → "z".
3. dog → "d" and "do" are shared; "dog" is unique → "dog".
4. duck → "du" is unique → "du". dove → "dov" is the first unique prefix → "dov".

Output: ["z", "dog", "du", "dov"]

Common Pitfalls

• Always emit at least the full word when no shorter prefix is unique (duplicate words fall into this case).
• Count every proper prefix of every word in the first pass — skipping the last character leaves full-word uniqueness untracked.
• Result order must match input order, not sorted-dictionary order.
• This is the same idea as a frequency trie; the rolling key is only a compact map key for those trie paths.

Shortest Unique Prefix for Every Word.java

Java


import java.util.*;

class Solution {

    // Approach: Count every prefix of every word using a rolling integer key
    // (each next character is packed with encode). A prefix is unique when its
    // count is exactly 1. For each word, grow the prefix until that count is 1
    // (or the whole word is consumed) and emit that shortest unique prefix.
    // Complexity: O(total characters) time and O(total characters) space for the
    // prefix frequency map.
    public ArrayList<String> findPrefixes(String[] arr) {
        Map<Integer, Integer> prefixCount = new HashMap<>();

        for (String word : arr) {
            int enc = 0;
            for (int i = 0; i < word.length(); i++) {
                enc = encode(enc, word.charAt(i));
                prefixCount.put(enc, prefixCount.getOrDefault(enc, 0) + 1);
            }
        }

        ArrayList<String> res = new ArrayList<>(arr.length);

        for (String word : arr) {
            int enc = 0;
            StringBuilder prefix = new StringBuilder();

            for (int i = 0; i < word.length(); i++) {
                enc = encode(enc, word.charAt(i));
                prefix.append(word.charAt(i));

                if (prefixCount.get(enc) == 1 || i == word.length() - 1) {
                    res.add(prefix.toString());
                    break;
                }
            }
        }

        return res;
    }

    int encode(int prev, int d) {
        return (prev << 5) + d;
    }
}

Was this solution helpful?