DSA 450 Notes

Problem Statement

Given an array of words, find the shortest unique prefix for each word such that no two prefixes are the same. Each prefix should uniquely identify its corresponding word from the rest.

Example:

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

Explanation:
- "z" is enough to uniquely identify "zebra" (no other word starts with 'z')
- "dog" needs all 3 chars (since "d", "do" are shared with duck/dove)
- "du" uniquely identifies "duck"
- "dov" uniquely identifies "dove"

Noob-Friendly Explanation

Imagine you're at a school and every student has a name tag. Instead of writing the full name, you want to write the shortest nickname that still uniquely identifies each student.

If the students are "Zebra", "Dog", "Duck", and "Dove":

"Zebra" can just be "Z" — no one else starts with Z!
"Dog", "Duck", "Dove" all start with "D", so "D" alone isn't enough
"Dog" starts with "Do" but so does "Dove", so we need "Dog" (the full word)
"Duck" starts with "Du" — no one else does, so "Du" is enough
"Dove" starts with "Dov" — that's unique too!

A Trie helps us figure this out: we count how many words pass through each node. The moment a node is visited by only one word, that prefix is the unique one!

Approach 1: Brute Force

Intuition

For each word, try increasing prefixes (length 1, 2, 3...) and check if any other word shares that prefix. The first prefix that no other word shares is the answer.

Algorithm

For each word, start with prefix of length 1
Check if any other word starts with the same prefix
If yes, increase prefix length by 1 and repeat
If no, this prefix is the shortest unique prefix

java

import java.util.*;

class Solution {
    public static String[] shortestUniquePrefixes(String[] words) {
        int n = words.length;
        String[] result = new String[n];

        for (int i = 0; i < n; i++) {
            String prefix = "";
            for (int len = 1; len <= words[i].length(); len++) {
                prefix = words[i].substring(0, len);
                boolean unique = true;
                for (int j = 0; j < n; j++) {
                    if (i != j && words[j].startsWith(prefix)) {
                        unique = false;
                        break;
                    }
                }
                if (unique) {
                    break;
                }
            }
            result[i] = prefix;
        }

        return result;
    }

    public static void main(String[] args) {
        String[] words = {"zebra", "dog", "duck", "dove"};
        String[] res = shortestUniquePrefixes(words);
        System.out.println(Arrays.toString(res)); // [z, dog, du, dov]
    }
}

Complexity Analysis

Time Complexity: O(N^2 * L) — For each word, we compare with all other words, each comparison up to length L
Space Complexity: O(N * L) — Storing the result prefixes

Approach 2: Optimal (Trie with Frequency Count)

Intuition

Build a Trie and store a count at each node representing how many words pass through it. For each word, traverse the Trie and stop at the first node where count is 1 — that means only this word passes through that node, making it a unique prefix.

Algorithm

Build a Trie from all words, incrementing a counter at each node during insertion
For each word, traverse the Trie character by character
Stop at the first node where count == 1
The path from root to this node is the shortest unique prefix

java

import java.util.*;

class Solution {

    static class TrieNode {
        TrieNode[] children;
        int count; // how many words pass through this node

        public TrieNode() {
            children = new TrieNode[26];
            count = 0;
        }
    }

    static TrieNode root;

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

    public static String getShortestUniquePrefix(String word) {
        TrieNode current = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            current = current.children[index];
            prefix.append(word.charAt(i));
            if (current.count == 1) {
                return prefix.toString();
            }
        }
        return prefix.toString();
    }

    public static String[] shortestUniquePrefixes(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            insert(word);
        }

        String[] result = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            result[i] = getShortestUniquePrefix(words[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        String[] words = {"zebra", "dog", "duck", "dove"};
        String[] res = shortestUniquePrefixes(words);
        System.out.println(Arrays.toString(res)); // [z, dog, du, dov]
    }
}

Complexity Analysis

Time Complexity: O(N * L) — Insert all words in O(N * L), then find prefix for each word in O(L)
Space Complexity: O(N * L * 26) — Trie nodes, each with 26 children slots

Key Takeaways

Frequency Count in Trie: By counting how many words pass through each node, we can find unique points
count == 1: The first node with count 1 means only one word goes through it — that's our unique prefix
Real-world Use: Shortest unique prefixes are used in autocomplete systems and command-line tab completion

Find shortest unique prefix for every word in a given list

Problem Statement

Noob-Friendly Explanation

Approach 1: Brute Force

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Trie with Frequency Count)

Intuition

Algorithm

Complexity Analysis

Key Takeaways