Longest Word in Dictionary

📋

Longest Word in Dictionary

Edge cases:

</>

IDE

def longestWord(words: list[str]) -> str:public String longestWord(String[] words)string longestWord(vector<string> &words)function longestWord(words)

def longestWord(words):
    # Write your solution here
    pass

class Solution {
    public String longestWord(String[] words) {
        // Write your solution here
        return "";
    }
}

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

string longestWord(vector<string> &words) {
    // Write your solution here
    return "";
}

function longestWord(words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: worldReturning a word without verifying all prefixes exist (e.g., missing prefix check).✅ Add a loop to check every prefix substring of the candidate word exists in the set before updating longest.

Wrong: applyIgnoring lexicographical order tie-break when multiple longest words exist.✅ When lengths tie, compare words lex order and choose the smaller one.

Wrong: bcaOff-by-one error in prefix substring extraction causing invalid prefixes to be accepted.✅ Ensure prefix substrings are correctly extracted from index 0 to i-1 for all i in 1..len(word)-1.

Wrong: aFailing to handle empty input by returning default or error instead of empty string.✅ Add explicit check for empty input and return empty string immediately.

Wrong: TLEUsing brute force O(n*m^2) prefix checks causing timeout on large inputs.✅ Use trie or prefix set with BFS or sorting to achieve O(n*m) complexity.

✓

Test Cases

Try testing your solution on empty and minimal inputs to ensure base cases are handled.

Consider tricky cases where greedy or partial prefix checks fail; test carefully.

Optimize your prefix checking approach to avoid timeouts on large inputs.

t1_01basic

Input{"words":["w","wo","wor","worl","world"]}

Expected"world"

⏱ Performance - must finish in 2000ms

All prefixes of "world" ("w", "wo", "wor", "worl") are in the list, so "world" is the longest valid word.

💡 Check if all prefixes of a word exist in the dictionary.

💡 Use a set or trie to quickly verify prefixes for each word.

💡 Return the longest word with all prefixes present; if tie, choose lex smallest.

Why it failed: Failed on canonical example: likely missing prefix checks or incorrect lex order tie-break. Fix by verifying every prefix exists before updating longest word.

✓ Correctly handles canonical example with prefix checks and lex order tie-break.

t1_02basic

Input{"words":["a","ap","app","appl","apple","apply","banana"]}

Expected"apple"

⏱ Performance - must finish in 2000ms

Both "apple" and "apply" have all prefixes present, but "apple" is lexicographically smaller, so it is returned.

💡 Check all prefixes for each candidate word.

💡 Compare words by length first, then lex order if lengths tie.

💡 Return the lexicographically smallest word among longest valid words.

Why it failed: Incorrect output due to ignoring lex order tie-break or incomplete prefix validation. Fix by comparing lex order when lengths tie and ensuring all prefixes exist.

✓ Correctly returns lex smallest longest word with all prefixes.

t2_01edge

Input{"words":[]}

Expected""

⏱ Performance - must finish in 2000ms

Empty input array means no words, so output is empty string.

💡 Consider what happens if the input list is empty.

💡 No words means no prefixes can exist.

💡 Return empty string when input is empty.

Why it failed: Fails empty input by returning non-empty string or error. Fix by adding a check for empty input and returning "" immediately.

✓ Correctly returns empty string for empty input.

t2_02edge

Input{"words":["a","b","c"]}

Expected"a"

⏱ Performance - must finish in 2000ms

All words are single letters; the lexicographically smallest letter "a" is returned.

💡 When all words are single letters, check lex order.

💡 No prefixes beyond the single letter itself.

💡 Return the lex smallest letter among all single-letter words.

Why it failed: Fails single-letter input by not returning lex smallest or by requiring prefixes that don't exist. Fix by allowing single-letter words as valid and choosing lex smallest.

✓ Correctly returns lex smallest single-letter word.

t2_03edge

Input{"words":["a","ar","art","arti","artic","artich","articha","artichau","artichaut"]}

Expected"artichaut"

⏱ Performance - must finish in 2000ms

No word has all prefixes present because some prefixes like "artichau" are missing, so output is empty string.

💡 Check carefully if all prefixes exist for each word.

💡 Missing any prefix invalidates the word.

💡 Return empty string if no word meets prefix condition.

Why it failed: Fails by returning a word with missing prefixes. Fix by verifying all prefixes exist before accepting a word.

✓ Correctly returns empty string when no word has all prefixes.

t2_04edge

Input{"words":["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]}

Expected"a"

⏱ Performance - must finish in 2000ms

All words are single letters; the lexicographically smallest letter "a" is returned.

💡 Check lex order when all words are single letters.

💡 No prefixes beyond the single letter itself.

💡 Return the lex smallest letter among all single-letter words.

Why it failed: Fails by not returning lex smallest single-letter word. Fix by comparing all single-letter words lex order and returning smallest.

✓ Correctly returns lex smallest single-letter word.

t3_01corner

Input{"words":["a","ab","abc","abd","abde","abdef"]}

Expected"abdef"

⏱ Performance - must finish in 2000ms

"abc" and "abd" have all prefixes present. "abde" is invalid because prefix "abd" is missing. "abc" is the longest valid word with all prefixes.

💡 Check all prefixes for each word, not just partial prefixes.

💡 Beware of greedy approach picking first longest word without full prefix check.

💡 Return the longest word with all prefixes present, not just longest word.

Why it failed: Fails greedy trap by returning "abdef" or "abd" without verifying all prefixes. Fix by checking every prefix for each candidate word.

✓ Correctly avoids greedy trap and returns longest valid word.

t3_02corner

Input{"words":["a","aa","aaa","aaaa","aaaaa"]}

Expected"aaaaa"

⏱ Performance - must finish in 2000ms

All prefixes of "aaaaa" exist, testing handling of repeated characters and prefix checks.

💡 Ensure prefix checks handle repeated characters correctly.

💡 Do not confuse 0/1 knapsack style counting with prefix existence.

💡 Verify each prefix substring is present in the set.

Why it failed: Fails by confusing prefix existence with frequency or by off-by-one errors in prefix checks. Fix by checking prefix substrings correctly.

✓ Correctly handles repeated characters and prefix checks.

t3_03corner

Input{"words":["a","b","ba","bca","bcae","bcaf"]}

Expected"ba"

⏱ Performance - must finish in 2000ms

"ba" is the longest word with all prefixes present; "bca" is invalid because prefix "bc" is missing.

💡 Check prefix existence carefully for each word.

💡 Beware of off-by-one errors in prefix substring extraction.

💡 Return empty string if no word meets prefix condition.

Why it failed: Fails by returning "bca" or longer invalid words missing prefixes. Fix by verifying all prefixes exist for each candidate word.

✓ Correctly returns longest valid word with all prefixes.

t4_01performance

Input{"words":["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa","aaaaaaaaaaaaaa","aaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 words, each up to length 30; solution must run in O(n*m) time within 2 seconds.

💡 Use a trie or set for efficient prefix checks.

💡 Avoid nested loops that check prefixes naively.

💡 Implement BFS or sorting with prefix validation for O(n*m) complexity.

Why it failed: TLE due to brute force O(n*m^2) prefix checks. Fix by using trie or prefix set with BFS or sorting to achieve O(n*m) complexity.

✓ Efficient O(n*m) solution confirmed by passing performance test.

Practice

1. Given the following code snippet implementing the trie-based autocomplete, and the input products = ["mobile", "mouse", "moneypot"] and searchWord = "mo", what is the value of the variable result after processing the entire searchWord?

easy

A. [["mobile", "moneypot", "mouse"], ["moneypot", "mobile", "mouse"]]

B. [["mobile", "moneypot", "mouse"], ["mobile", "moneypot", "mouse"]]

C. [["mobile", "mouse", "moneypot"], ["mobile", "mouse", "moneypot"]]

D. [["mobile", "mouse", "moneypot"], ["mouse", "mobile", "moneypot"]]

Solution

1. Step 1: Sort products lexicographically

   Sorted products: ["mobile", "moneypot", "mouse"]

2. Step 2: Build trie and collect suggestions

   For prefix 'm': suggestions are ["mobile", "moneypot", "mouse"]. For prefix 'mo': same suggestions as all start with 'mo'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result matches expected suggestions for prefixes 'm' and 'mo' [OK]

Hint: Sorted products determine suggestion order at each prefix [OK]

Common Mistakes:

• Mixing order of suggestions
• Off-by-one in prefix traversal
• Appending suggestions after node moves

2. You are given a list of words and need to find the shortest prefix for each word that uniquely identifies it among all words. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Build a trie where each node tracks how many words pass through it, then find the prefix where frequency is 1.

B. Sort the words and compare only adjacent words to find the shortest unique prefix.

C. Compare each word's prefixes pairwise with all other words to find uniqueness.

D. Use dynamic programming to store prefix uniqueness states for all words.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding shortest unique prefixes efficiently for all words, which suggests a data structure that can share prefixes.

2. Step 2: Evaluate approaches

   Brute force (A) is too slow (O(n^2 * m)). Sorting + adjacent comparison (C) can miss conflicts with non-adjacent words. DP (D) is not a natural fit here. Trie with frequency counts (B) efficiently tracks prefix usage and finds unique prefixes in O(n*m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie frequency counting matches problem needs [OK]

Hint: Trie frequency counts track prefix uniqueness efficiently [OK]

Common Mistakes:

• Assuming sorting adjacent words is sufficient for uniqueness
• Trying brute force despite inefficiency

3. Given a string s and a dictionary of words, you want to determine if s can be segmented into a sequence of dictionary words. Which approach guarantees an optimal solution that efficiently checks prefixes and avoids repeated substring checks?

easy

A. Greedy approach that picks the longest matching prefix at each step

B. Iterative dynamic programming combined with a trie to check prefixes efficiently

C. Pure brute force recursion checking all substring partitions without memoization

D. Sorting the dictionary and using binary search to check substrings

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if the string can be segmented into dictionary words, which involves many substring checks.

2. Step 2: Evaluate approaches for efficiency

   Greedy fails because longest prefix may not lead to a solution; brute force is exponential; binary search is inefficient for substring checks. Using a trie with DP allows prefix checks in O(m) time per position, avoiding repeated substring checks.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie + DP efficiently prunes invalid prefixes [OK]

Hint: Trie + DP avoids repeated substring checks [OK]

Common Mistakes:

• Assuming greedy longest prefix always works
• Using brute force without memoization
• Using binary search for substring checks

4. Consider the following buggy Trie insert method. Which line contains the subtle bug that causes search to fail for inserted words?

medium

A. Line where node = self.root is assigned

B. Line where node = node.children[ch] is assigned inside the loop

C. Line where isEnd flag should be set but is missing

D. Line where the if condition checks if ch not in node.children

Solution

1. Step 1: Identify missing isEnd flag set

   After inserting all characters, isEnd must be set true to mark word end. This line is missing.

2. Step 2: Understand impact on search

   Without isEnd=true, search returns false even if path exists, because node.isEnd remains false.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing isEnd assignment causes search failure for inserted words [OK]

Hint: isEnd must be set after inserting entire word [OK]

Common Mistakes:

• Forgetting to mark isEnd after insertion

5. Suppose the MapSum data structure must support keys being inserted multiple times with updated values, and sum queries with an empty prefix should return the total sum of all keys. Which modification to the optimal trie-based solution correctly handles this?

hard

A. Return 0 immediately if prefix is empty, since no keys match empty prefix.

B. Use a separate hash map to sum all values and ignore trie sums for empty prefix queries.

C. Store and update a sum at the root node representing total sum of all keys, and return root.sum when prefix is empty.

D. Traverse all children of root node and sum their sums recursively on empty prefix queries.

Solution

1. Step 1: Understand empty prefix sum requirement

   Empty prefix means sum of all keys, so root node sum must represent total sum.

2. Step 2: Check how root sum is maintained

   Root.sum is updated on every insert with delta, so returning root.sum for empty prefix is correct and efficient.

3. Step 3: Evaluate other options

   Returning 0 is incorrect. Separate hash map duplicates data and is inefficient. Recursive traversal is costly and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Root sum stores total sum, perfect for empty prefix queries [OK]

Hint: Root node sum holds total sum for empty prefix queries [OK]

Common Mistakes:

• Returning 0 for empty prefix
• Not updating root sum on insert
• Using costly recursive sum on empty prefix