Minimum Prefix for Each String
Filed under Amazon
Free read 3 of 3Confirm what happens if a word is a prefix of another word (the prefix must be the full word itself).
The question
Given a list of strings, find the shortest unique prefix for each string in the list.
Constraints
- List contains between 1 and 10^4 strings.
- Strings consist of lowercase English letters.
- All strings in the input are unique.
Examples
- Input
- words = ["zebra", "dog", "duck", "dove"]
- Output
- ["z", "dog", "du", "dov"]
- Why
- "zebra" is the only word starting with 'z'. "dog" is unique. "duck" and "dove" share 'du', so they need 'duc'/'duck' and 'dov'.
Approach
Confirm what happens if a word is a prefix of another word (the prefix must be the full word itself).
For each string, check prefixes of increasing length until a prefix is found that does not match any other string's prefix. Time complexity: O(N^2 * M).
Insert all words into a Trie where each node stores the count of how many times it was visited. Then, traverse the Trie to find the shortest prefix with a visit count of 1 for each word. Time complexity: O(N * M).
Duplicate strings in input (though usually unique), single character strings, or identical prefixes.
Tips
- What they are testing: Test with words where one word is a complete prefix of another (e.g., 'car', 'card').
- Common mistake: Attempting a naive pairwise comparison instead of using a Trie data structure.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.