197. Find the Shortest Unique Prefix for Every Word

Given n distinct words, find, for each word, its shortest prefix that is not a prefix of any other word in the list. If no such prefix exists within the word's own length (every one of its prefixes, including its full length, is shared with some other word), use the entire word itself. Print the answers in the same order as the input words, space-separated.

Input: The first line contains an integer n, followed by n lines each containing one distinct word. Output: Print the shortest unique prefix for each word, in the same order as the input, space-separated on one line.

1 <= n <= 10^5

The 'use the whole word if no unique-count node is found' fallback matters - if a word is a genuine PREFIX of another word entirely (like 'do' if 'dog' didn't exist but something else started with 'do'), you need this fallback to still produce a valid, correct answer.

For every word in a list, find the SHORTEST beginning chunk of it that no other word in the list also starts with - basically, the minimum you'd need to type before autocomplete could uniquely identify just that one word. Brute force: For each word, try every possible prefix length starting from 1, and for each length, check directly against every OTHER word whether they share that same prefix - this costs roughly O(n² * word length), too slow for large word lists. Optimised: By tracking a pass-through count at every trie node (exactly like the 'Count Words With a Given Prefix' problem earlier in this category), finding each word's shortest unique prefix becomes a single walk down its own path, stopping the instant the count reaches 1 - no comparison against other words individually needed at all, since the trie's shared structure already encodes exactly how many words share any given prefix.

Sort all n words lexicographically. The key insight is that the word sharing the longest common prefix with any given word must be lexicographically adjacent to it in sorted order, so we only need to compare each word against its immediate predecessor and successor in the sorted list instead of against all n-1 other words. For each word, compute the longest common prefix (LCP) length with its previous and next neighbor, take the maximum of the two, and the unique prefix is one character longer than that. This cuts the comparison work down from O(n) neighbors per word to O(1) neighbors, at the cost of needing a sort first. Time: O(n log n * L) Space: O(n * L)

For each word, try every prefix length from 1 up to its full length, and for each candidate prefix scan through all the other n-1 words to check whether any of them also starts with that prefix. The shortest prefix length at which no other word matches is the answer; if every prefix (including the full word) is shared, fall back to the full word. This works because it directly checks the definition of 'unique prefix' by brute enumeration, but comparing every prefix of every word against every other word costs O(n^2 * L) time, which is far too slow for n up to 1e5. Time: O(n^2 * L) Space: O(1) extra

Insert all n words into a trie where every node stores how many words pass through it. Then, for each word, walk down its path in the trie from the root and stop at the first node whose count is exactly 1 - the prefix ending there is guaranteed unique to that word (or if none exists, the full word itself). This works because a node's count directly tells you how many words share that prefix, so you never need to explicitly compare words against each other; the trie structure encodes all the sharing information once during construction, giving a single linear pass over all characters instead of any sorting or pairwise comparison. Time: O(total number of characters) Space: O(total number of characters * 26)

1. Build a trie from all the words, tracking at every node how many words pass through that exact point. 2. For each word, walk down its own path in the trie, character by character. 3. Stop at the FIRST node where the pass-through count drops to exactly 1 - meaning only this one word continues through here, nothing else does. 4. The path up to and including that node is the shortest unique prefix; if you reach the word's full length without ever hitting a count of 1, the entire word itself is the answer.

Time: Building the trie takes time proportional to the total characters across all words; finding every word's answer afterward takes time proportional to that same total, since each word's walk is bounded by its own length. Space: Proportional to the total characters across all words, for the trie structure.

Test a word sharing no prefix with any other (answer is just its first character), a word that is a full prefix of another (may need its entire length), and n=10^5 for performance.

This problem is a great showcase of reusing the exact same 'pass-through count per node' trick from a simpler earlier problem to solve a seemingly harder one - a strong signal of building and reusing a toolkit rather than solving every problem from first principles.