Shortest Unique Prefix for Every Word

🎯

Shortest Unique Prefix for Every Word

mediumTRIEAmazonGoogleBloomberg

Imagine you are building an autocomplete system that needs to quickly identify each word uniquely by the shortest prefix possible, saving typing effort and improving user experience.

💡 This problem is about finding the shortest prefix for each word that no other word shares. Beginners often struggle because they try to compare prefixes pairwise, which is inefficient. Understanding tries helps efficiently track prefix frequencies and find uniqueness.

📋

Problem Statement

Given a list of words, find the shortest unique prefix for every word. The shortest unique prefix of a word is the smallest prefix which is not shared by any other word in the list. Return the list of shortest unique prefixes in the same order as the input words.

1 ≤ n ≤ 10^5 (number of words)1 ≤ length of each word ≤ 100Words contain only lowercase English letters

💡

Example

Input["zebra","dog","duck","dove"]

Outputzdogdudov

For 'zebra', 'z' is unique. For 'dog', 'dog' itself is unique since 'd' and 'do' are shared with 'duck' and 'dove'. For 'duck', 'du' is unique. For 'dove', 'dov' is unique.

• All words are identical → shortest unique prefix is the entire word
• Words with one character → prefix is the character itself
• Words where one is prefix of another → longer word's prefix must be longer
• Empty list → return empty list

⚠️

Common Mistakes

Not incrementing frequency at each trie node during insertion

Unique prefix detection fails, returning incorrect prefixes

✅ Ensure frequency is incremented at every node traversed during insertion

Comparing prefixes only with previous word after sorting, ignoring next word

Incorrect prefix length, missing conflicts with next word

✅ Compare with both previous and next words to find max common prefix

Returning prefix length longer than word length

Index out of range errors or incorrect prefixes

✅ Cap prefix length to word length and handle edge cases

Not mapping prefixes back to original word order after sorting

Output prefixes in sorted order, not matching input order

✅ Use a map from word to prefix and output in original order

Using global variables or mutable default arguments in Python trie implementation

Unexpected behavior or bugs in multiple test runs

✅ Initialize variables inside methods or constructors properly

🧠

Brute Force (Pairwise Prefix Comparison)

💡 This approach exists to build intuition by directly comparing prefixes of every pair of words, showing why naive methods are inefficient and motivating trie usage.

Intuition

For each word, compare it with every other word to find the minimum prefix length that differs. The shortest unique prefix is the smallest prefix that no other word shares.

Algorithm

1. For each word in the list:
2. Initialize prefix length to 1
3. For every other word, compare prefixes character by character
4. Increase prefix length until the prefix is unique compared to all others
5. Return the prefixes found for all words

💡 The nested loops and character comparisons make it hard to see efficiency; it’s a direct, exhaustive search.

</>

Code

def shortest_unique_prefix(words):
    n = len(words)
    result = []
    for i in range(n):
        prefix_len = 1
        while prefix_len <= len(words[i]):
            prefix = words[i][:prefix_len]
            unique = True
            for j in range(n):
                if i != j and words[j].startswith(prefix):
                    unique = False
                    break
            if unique:
                break
            prefix_len += 1
        result.append(words[i][:prefix_len])
    return result

# Driver code
if __name__ == '__main__':
    words = ["zebra", "dog", "duck", "dove"]
    print(shortest_unique_prefix(words))

Line Notes

for i in range(n):Iterate over each word to find its unique prefix

prefix_len = 1Start checking prefixes from length 1

for j in range(n):Compare current word's prefix with all other words

if i != j and words[j].startswith(prefix):Check if another word shares the prefix, making it non-unique

import java.util.*;
public class ShortestUniquePrefix {
    public static List<String> shortestUniquePrefix(List<String> words) {
        int n = words.size();
        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int prefixLen = 1;
            String word = words.get(i);
            while (prefixLen <= word.length()) {
                String prefix = word.substring(0, prefixLen);
                boolean unique = true;
                for (int j = 0; j < n; j++) {
                    if (i != j && words.get(j).startsWith(prefix)) {
                        unique = false;
                        break;
                    }
                }
                if (unique) break;
                prefixLen++;
            }
            result.add(word.substring(0, prefixLen));
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("zebra", "dog", "duck", "dove");
        System.out.println(shortestUniquePrefix(words));
    }
}

Line Notes

for (int i = 0; i < n; i++) {Loop over each word to find its unique prefix

int prefixLen = 1;Start with prefix length 1

for (int j = 0; j < n; j++) {Compare prefix with all other words

if (i != j && words.get(j).startsWith(prefix)) {Check if prefix is shared with another word

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> shortestUniquePrefix(const vector<string>& words) {
    int n = words.size();
    vector<string> result;
    for (int i = 0; i < n; i++) {
        int prefixLen = 1;
        while (prefixLen <= (int)words[i].size()) {
            string prefix = words[i].substr(0, prefixLen);
            bool unique = true;
            for (int j = 0; j < n; j++) {
                if (i != j && words[j].compare(0, prefixLen, prefix) == 0) {
                    unique = false;
                    break;
                }
            }
            if (unique) break;
            prefixLen++;
        }
        result.push_back(words[i].substr(0, prefixLen));
    }
    return result;
}

int main() {
    vector<string> words = {"zebra", "dog", "duck", "dove"};
    vector<string> prefixes = shortestUniquePrefix(words);
    for (auto& p : prefixes) cout << p << " ";
    cout << endl;
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Iterate over each word to find its unique prefix

int prefixLen = 1;Start checking prefixes from length 1

for (int j = 0; j < n; j++) {Compare prefix with all other words

if (i != j && words[j].compare(0, prefixLen, prefix) == 0) {Check if prefix matches another word's prefix

function shortestUniquePrefix(words) {
    const n = words.length;
    const result = [];
    for (let i = 0; i < n; i++) {
        let prefixLen = 1;
        while (prefixLen <= words[i].length) {
            const prefix = words[i].substring(0, prefixLen);
            let unique = true;
            for (let j = 0; j < n; j++) {
                if (i !== j && words[j].startsWith(prefix)) {
                    unique = false;
                    break;
                }
            }
            if (unique) break;
            prefixLen++;
        }
        result.push(words[i].substring(0, prefixLen));
    }
    return result;
}

// Test
const words = ["zebra", "dog", "duck", "dove"];
console.log(shortestUniquePrefix(words));

Line Notes

for (let i = 0; i < n; i++) {Loop over each word to find its unique prefix

let prefixLen = 1;Start with prefix length 1

for (let j = 0; j < n; j++) {Compare prefix with all other words

if (i !== j && words[j].startsWith(prefix)) {Check if prefix is shared with another word

⏱

Complexity

TimeO(n^2 * m) where n is number of words and m is max word length

SpaceO(n * m) for output storage

For each of the n words, we compare prefixes with up to n-1 other words, each comparison up to m characters.

💡 For n=1000 and m=10, this means about 10 million comparisons, which is too slow for large inputs.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Sorting + Adjacent Comparison

💡 Sorting words groups similar prefixes together, so only adjacent words need to be compared, reducing comparisons drastically.

Intuition

After sorting, only neighbors can share prefixes. For each word, compare with previous and next word to find the minimum prefix length that differs.

Algorithm

1. Sort the list of words lexicographically
2. For each word, compare with previous and next word to find the longest common prefix length
3. The shortest unique prefix length is one more than the max common prefix length with neighbors
4. Return the prefixes of that length for all words

💡 Sorting reduces the problem to local checks, but careful indexing and prefix length calculation is needed.

</>

Code

def shortest_unique_prefix(words):
    n = len(words)
    sorted_words = sorted([(w, i) for i, w in enumerate(words)])
    prefix_lengths = [0] * n

    def common_prefix_len(a, b):
        length = 0
        for x, y in zip(a, b):
            if x == y:
                length += 1
            else:
                break
        return length

    for i in range(n):
        prev_len = common_prefix_len(sorted_words[i][0], sorted_words[i-1][0]) if i > 0 else 0
        next_len = common_prefix_len(sorted_words[i][0], sorted_words[i+1][0]) if i < n-1 else 0
        prefix_lengths[sorted_words[i][1]] = max(prev_len, next_len) + 1

    return [words[i][:prefix_lengths[i]] for i in range(n)]

# Driver code
if __name__ == '__main__':
    words = ["zebra", "dog", "duck", "dove"]
    print(shortest_unique_prefix(words))

Line Notes

sorted_words = sorted([(w, i) for i, w in enumerate(words)])Sort words with original indices to preserve order

def common_prefix_len(a, b):Helper to find length of common prefix between two words

prev_len = common_prefix_len(sorted_words[i][0], sorted_words[i-1][0])Compare with previous word if exists

prefix_lengths[sorted_words[i][1]] = max(prev_len, next_len) + 1Store prefix length at original index

import java.util.*;
public class ShortestUniquePrefix {
    private static int commonPrefixLen(String a, String b) {
        int len = 0;
        int limit = Math.min(a.length(), b.length());
        for (int i = 0; i < limit; i++) {
            if (a.charAt(i) == b.charAt(i)) len++;
            else break;
        }
        return len;
    }

    public static List<String> shortestUniquePrefix(List<String> words) {
        int n = words.size();
        List<Pair> sortedWords = new ArrayList<>();
        for (int i = 0; i < n; i++) sortedWords.add(new Pair(words.get(i), i));
        Collections.sort(sortedWords, Comparator.comparing(p -> p.word));

        int[] prefixLengths = new int[n];
        for (int i = 0; i < n; i++) {
            int prevLen = i > 0 ? commonPrefixLen(sortedWords.get(i).word, sortedWords.get(i - 1).word) : 0;
            int nextLen = i < n - 1 ? commonPrefixLen(sortedWords.get(i).word, sortedWords.get(i + 1).word) : 0;
            prefixLengths[sortedWords.get(i).index] = Math.max(prevLen, nextLen) + 1;
        }

        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String w = words.get(i);
            int len = prefixLengths[i];
            if (len > w.length()) len = w.length();
            result.add(w.substring(0, len));
        }
        return result;
    }

    static class Pair {
        String word;
        int index;
        Pair(String w, int i) { word = w; index = i; }
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("zebra", "dog", "duck", "dove");
        System.out.println(shortestUniquePrefix(words));
    }
}

Line Notes

Collections.sort(sortedWords, Comparator.comparing(p -> p.word));Sort words with original indices to preserve order

int prevLen = i > 0 ? commonPrefixLen(...) : 0;Find common prefix length with previous word

prefixLengths[sortedWords.get(i).index] = Math.max(prevLen, nextLen) + 1;Store prefix length at original index

result.add(w.substring(0, len));Add prefix substring to result preserving input order

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int commonPrefixLen(const string& a, const string& b) {
    int len = 0;
    int limit = min(a.size(), b.size());
    for (int i = 0; i < limit; i++) {
        if (a[i] == b[i]) len++;
        else break;
    }
    return len;
}

vector<string> shortestUniquePrefix(const vector<string>& words) {
    int n = words.size();
    vector<pair<string, int>> sortedWords;
    for (int i = 0; i < n; i++) sortedWords.emplace_back(words[i], i);
    sort(sortedWords.begin(), sortedWords.end(), [](auto& a, auto& b) { return a.first < b.first; });

    vector<int> prefixLengths(n);
    for (int i = 0; i < n; i++) {
        int prevLen = i > 0 ? commonPrefixLen(sortedWords[i].first, sortedWords[i - 1].first) : 0;
        int nextLen = i < n - 1 ? commonPrefixLen(sortedWords[i].first, sortedWords[i + 1].first) : 0;
        prefixLengths[sortedWords[i].second] = max(prevLen, nextLen) + 1;
    }

    vector<string> result(n);
    for (int i = 0; i < n; i++) {
        int len = prefixLengths[i];
        if (len > (int)words[i].size()) len = words[i].size();
        result[i] = words[i].substr(0, len);
    }
    return result;
}

int main() {
    vector<string> words = {"zebra", "dog", "duck", "dove"};
    vector<string> prefixes = shortestUniquePrefix(words);
    for (auto& p : prefixes) cout << p << " ";
    cout << endl;
    return 0;
}

Line Notes

sort(sortedWords.begin(), sortedWords.end(), [](auto& a, auto& b) { return a.first < b.first; });Sort words with original indices to preserve order

int prevLen = i > 0 ? commonPrefixLen(...) : 0;Calculate common prefix length with previous word

prefixLengths[sortedWords[i].second] = max(prevLen, nextLen) + 1;Store prefix length at original index

result[i] = words[i].substr(0, len);Assign prefix substring preserving input order

function commonPrefixLen(a, b) {
    let len = 0;
    let limit = Math.min(a.length, b.length);
    for (let i = 0; i < limit; i++) {
        if (a[i] === b[i]) len++;
        else break;
    }
    return len;
}

function shortestUniquePrefix(words) {
    const sortedWords = words.map((w, i) => [w, i]).sort((a, b) => a[0].localeCompare(b[0]));
    const n = sortedWords.length;
    const prefixLengths = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        const prevLen = i > 0 ? commonPrefixLen(sortedWords[i][0], sortedWords[i - 1][0]) : 0;
        const nextLen = i < n - 1 ? commonPrefixLen(sortedWords[i][0], sortedWords[i + 1][0]) : 0;
        prefixLengths[sortedWords[i][1]] = Math.max(prevLen, nextLen) + 1;
    }

    return words.map((w, i) => w.substring(0, prefixLengths[i]));
}

// Test
const words = ["zebra", "dog", "duck", "dove"];
console.log(shortestUniquePrefix(words));

Line Notes

const sortedWords = words.map((w, i) => [w, i]).sort((a, b) => a[0].localeCompare(b[0]));Sort words with original indices to preserve order

const prevLen = i > 0 ? commonPrefixLen(...) : 0;Find common prefix length with previous word

prefixLengths[sortedWords[i][1]] = Math.max(prevLen, nextLen) + 1;Store prefix length at original index

return words.map((w, i) => w.substring(0, prefixLengths[i]));Return prefixes preserving input order

⏱

Complexity

TimeO(n log n * m) where n is number of words and m is max word length

SpaceO(n * m) for sorting and output

Sorting takes O(n log n * m) due to string comparisons; prefix comparisons are O(n * m).

💡 For n=100000 and m=10, sorting is feasible and much faster than brute force.

Interview Verdict: Accepted / Efficient for large inputs

This approach is a practical improvement and often acceptable in interviews if tries are not required.

🧠

Trie with Frequency Count at Nodes

💡 Using a trie to store all words and count how many words pass through each node allows quick identification of unique prefixes.

Intuition

Insert all words into a trie, incrementing frequency counts at each node. The shortest unique prefix for a word is the prefix up to the first node with frequency 1.

Algorithm

1. Create a trie node structure with children and frequency count
2. Insert all words into the trie, incrementing frequency at each node
3. For each word, traverse the trie until a node with frequency 1 is found
4. The prefix up to that node is the shortest unique prefix

💡 Understanding trie structure and frequency counting is key; traversal for prefix extraction is straightforward once built.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.freq = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.freq += 1

    def unique_prefix(self, word):
        node = self.root
        prefix = ''
        for ch in word:
            prefix += ch
            node = node.children[ch]
            if node.freq == 1:
                return prefix
        return prefix

def shortest_unique_prefix(words):
    trie = Trie()
    for w in words:
        trie.insert(w)
    return [trie.unique_prefix(w) for w in words]

# Driver code
if __name__ == '__main__':
    words = ["zebra", "dog", "duck", "dove"]
    print(shortest_unique_prefix(words))

Line Notes

self.children = {}Dictionary to store child nodes for each character

node.freq += 1Increment frequency to count how many words pass this node

if node.freq == 1:First node with frequency 1 indicates unique prefix

return [trie.unique_prefix(w) for w in words]Collect shortest unique prefixes for all words

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int freq = 0;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
            node.freq++;
        }
    }

    String uniquePrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (char ch : word.toCharArray()) {
            prefix.append(ch);
            node = node.children.get(ch);
            if (node.freq == 1) return prefix.toString();
        }
        return prefix.toString();
    }
}

public class ShortestUniquePrefix {
    public static List<String> shortestUniquePrefix(List<String> words) {
        Trie trie = new Trie();
        for (String w : words) trie.insert(w);
        List<String> result = new ArrayList<>();
        for (String w : words) result.add(trie.uniquePrefix(w));
        return result;
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("zebra", "dog", "duck", "dove");
        System.out.println(shortestUniquePrefix(words));
    }
}

Line Notes

Map<Character, TrieNode> children = new HashMap<>();Stores child nodes for each character

node.freq++;Increment frequency count for prefix tracking

if (node.freq == 1) return prefix.toString();Unique prefix found when frequency is 1

for (String w : words) result.add(trie.uniquePrefix(w));Retrieve shortest unique prefixes for all words

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    int freq = 0;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end())
                node->children[ch] = new TrieNode();
            node = node->children[ch];
            node->freq++;
        }
    }

    string uniquePrefix(const string& word) {
        TrieNode* node = root;
        string prefix;
        for (char ch : word) {
            prefix += ch;
            node = node->children[ch];
            if (node->freq == 1) return prefix;
        }
        return prefix;
    }
};

vector<string> shortestUniquePrefix(const vector<string>& words) {
    Trie trie;
    for (const auto& w : words) trie.insert(w);
    vector<string> result;
    for (const auto& w : words) result.push_back(trie.uniquePrefix(w));
    return result;
}

int main() {
    vector<string> words = {"zebra", "dog", "duck", "dove"};
    vector<string> prefixes = shortestUniquePrefix(words);
    for (auto& p : prefixes) cout << p << " ";
    cout << endl;
    return 0;
}

Line Notes

unordered_map<char, TrieNode*> children;Stores child nodes for each character

node->freq++;Increment frequency count for prefix uniqueness

if (node->freq == 1) return prefix;Return prefix when unique node found

for (const auto& w : words) result.push_back(trie.uniquePrefix(w));Get shortest unique prefixes for all words

class TrieNode {
    constructor() {
        this.children = new Map();
        this.freq = 0;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
            node = node.children.get(ch);
            node.freq++;
        }
    }

    uniquePrefix(word) {
        let node = this.root;
        let prefix = '';
        for (const ch of word) {
            prefix += ch;
            node = node.children.get(ch);
            if (node.freq === 1) return prefix;
        }
        return prefix;
    }
}

function shortestUniquePrefix(words) {
    const trie = new Trie();
    for (const w of words) trie.insert(w);
    return words.map(w => trie.uniquePrefix(w));
}

// Test
const words = ["zebra", "dog", "duck", "dove"];
console.log(shortestUniquePrefix(words));

Line Notes

this.children = new Map();Map to store child nodes for each character

node.freq++;Increment frequency count to track prefix usage

if (node.freq === 1) return prefix;Unique prefix found when frequency is 1

return words.map(w => trie.uniquePrefix(w));Retrieve shortest unique prefixes for all words

⏱

Complexity

TimeO(n * m) where n is number of words and m is max word length

SpaceO(n * m) for trie storage

Each word is inserted once, traversing m characters; prefix extraction is also O(m) per word.

💡 For n=100000 and m=10, this is efficient and scalable, ideal for large datasets.

Interview Verdict: Accepted / Optimal solution

This is the canonical solution for prefix uniqueness problems, demonstrating mastery of tries.

📊

All Approaches - One-Glance Tradeoffs

💡 The trie approach is best for coding in interviews due to optimal time and clarity. Sorting is a good fallback. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * m)	O(n * m)	No	Yes	Mention only - never code due to inefficiency
2. Sorting + Adjacent Comparison	O(n log n * m)	O(n * m)	No	Yes	Good if trie not allowed or for quick optimization
3. Trie with Frequency Count	O(n * m)	O(n * m)	No	Yes	Optimal approach to implement and explain

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to efficient solutions. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and constraints with the interviewerExplain the brute force approach and its inefficiencyIntroduce sorting-based optimization and discuss tradeoffsPresent the trie-based optimal solution with frequency countsCode the trie solution carefully, test with examples

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, knowledge of tries, and coding accuracy.

Common Follow-ups

• How to handle uppercase letters or other character sets → extend trie node children
• How to optimize space for large alphabets → use arrays or compressed tries
• Can you find unique suffixes instead → similar approach with reversed words
• How to handle dynamic insertion and queries → maintain trie with updates

💡 These follow-ups test your ability to adapt the solution to variations and real-world constraints.

🔍

Pattern Recognition

When to Use

1) Asked to find unique prefixes or minimal distinguishing prefixes; 2) Input is a list of strings; 3) Need efficient prefix queries; 4) Constraints allow trie or sorting

Signature Phrases

shortest unique prefixprefix that no other word sharesminimal prefix to identify word

NOT This Pattern When

Problems asking for substring uniqueness or suffix uniqueness are different patterns.

Similar Problems

Longest Common Prefix - related by prefix comparisonImplement Trie (Prefix Tree) - foundational for this problem

Practice

1. Consider the following Python code implementing a bit trie for maximum XOR queries. Given nums = [1, 2] inserted into the trie, what is the value of max_xor after calling max_xor(3)?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace insertion of nums 1 and 2

   Bits of 1 and 2 inserted from MSB to LSB into trie.

2. Step 2: Trace max_xor(3)

   For each bit of 3, try toggled bit in trie to maximize XOR. At highest differing bit, toggled bit exists, setting max_xor bits accordingly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   3 XOR 0 = 3, 3 XOR 1 = 2, 3 XOR 2 = 1; max is 3 [OK]

Hint: XOR with 3 and 0,1,2 yields max 3 [OK]

Common Mistakes:

• Confusing bit order in trie traversal
• Off-by-one in bit indexing
• Returning wrong max_xor value

2. Consider the following Python code snippet implementing the Trie + DFS approach for palindrome pairs. Given the input words = ["bat", "tab", "cat"], what is the final output of palindromePairs(words)?

easy

A. [[0, 1], [1, 0]]

B. [[1, 0], [0, 1]]

C. [[0, 1], [1, 0], [2, 2]]

D. []

Solution

1. Step 1: Trace add_word for "bat" and "tab"

   Words are added reversed: "tab" for "bat", "bat" for "tab". Palindrome suffixes recorded accordingly.

2. Step 2: Trace search for "bat" (index 0)

   Matches "tab" reversed in trie, finds palindrome suffixes leading to pair [0,1]. Similarly for "tab" (index 1) finds [1,0]. "cat" has no pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected palindrome pairs [OK]

Hint: Pairs are symmetric for "bat" and "tab" only [OK]

Common Mistakes:

• Confusing order of pairs
• Including self-pairs
• Missing palindrome suffix checks

3. What is the time complexity of the optimal Trie + DFS backtracking approach for finding palindrome pairs in a list of n words, each of maximum length k?

medium

A. O(n * k)

B. O(n^2 * k)

C. O(n * k * log n)

D. O(n * k^2)

Solution

1. Step 1: Identify outer and inner loops

   There are n words, each of length k. Trie insertion and search involve iterating over k characters.

2. Step 2: Analyze palindrome checks and DFS

   Palindrome checks on suffixes/prefixes cost O(k) each, done during insertion and search, leading to O(k^2) per word.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie + palindrome checks cause quadratic factor in k, linear in n [OK]

Hint: Palindrome checks inside loops cause k^2 factor [OK]

Common Mistakes:

• Assuming brute force O(n^2 * k)
• Ignoring palindrome check cost
• Confusing log n factor

4. Suppose the WordDictionary is extended to support searching for words with the wildcard '*' that matches zero or more characters (instead of '.' matching exactly one). Which of the following modifications to the trie search algorithm correctly handles '*' wildcard searches?

hard

A. Use recursion or stack to explore zero or more characters by branching at current node and advancing index accordingly.

B. Treat '*' as '.' and continue with single character branching only.

C. Precompute all possible expansions of '*' and store them in the trie during addWord.

D. Ignore '*' and treat it as a literal character during search.

Solution

1. Step 1: Understand '*' wildcard semantics

   '*' matches zero or more characters, so search must explore skipping '*' or consuming characters.

2. Step 2: Identify correct search strategy

   Using recursion or stack to explore both skipping '*' (index+1) and consuming children (index unchanged) correctly handles zero or more matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Branching on both skipping and consuming characters handles '*' wildcard [OK]

Hint: '*' requires branching on skip or consume [OK]

Common Mistakes:

• Treating '*' like '.'
• Precomputing expansions is infeasible
• Ignoring '*' wildcard semantics

5. Suppose the problem is modified so that each query asks for the maximum XOR with any array element less than or equal to m, but now elements can be reused multiple times per query. Which modification to the algorithm is correct?

hard

A. Use the same offline trie approach; reuse does not affect XOR calculation.

B. Reuse does not change the problem; just run brute force for each query.

C. Switch to a dynamic programming approach since reuse implies unlimited usage.

D. Modify the trie to store counts of elements and allow multiple traversals per query bit path.

Solution

1. Step 1: Understand reuse impact

   Reusing elements means multiple paths in trie may be valid; counts needed to track availability.

2. Step 2: Modify trie structure

   Store counts at nodes to allow multiple traversals and correct max XOR calculation with reuse.

3. Step 3: Reject naive approaches

   Offline trie without counts ignores reuse; DP or brute force inefficient or incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting elements in trie supports reuse [OK]

Hint: Track counts in trie nodes for reuse [OK]

Common Mistakes:

• Ignoring reuse effect on trie
• Assuming reuse is free without data structure changes
• Switching to DP unnecessarily