Longest String with All Prefixes
Solve this Problemwords, find the longest one that's "complete" — every one of its prefixes, from length 1 up to its own full length, must also appear somewhere in the list. If several words tie for longest, return the alphabetically smallest of them; if not a single word qualifies, return the literal string "None".
This is the same prefix-chain idea as building a word one character at a time: mark every trie node where some inserted word actually ends, then only ever walk into a child whose own node carries that mark. Any real node the walk reaches this way sits at the end of an unbroken chain of complete words. The one difference from a plain "longest buildable word" search is the empty starting point — the root itself is never a real candidate, so if the walk can't step into even a single child, nothing was complete and the answer falls back to "None" rather than an empty string.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ words.length ≤ 1000 - ◆
1 ≤ words[i].length ≤ 30 - ◆
words consists of lowercase English letters - ◆
words may contain duplicates
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Prefix with a Hash Set
BruteDrop every word into a hash set. For each word, check whether every one of its shorter prefixes (length 1 up to length − 1) is also in that set — only then does it count as "complete." Track the longest complete word seen, breaking ties alphabetically. If nothing ever qualifies, report "None" instead of a real word.
O(n · L²)O(n · L)1class Solution {
2 public String longestCompleteString(String[] words) {
3 Set<String> wordSet = new HashSet<>(Arrays.asList(words));
4 String best = null;
5 for (String word : words) {
6 boolean complete = true;
7 for (int i = 1; i < word.length(); i++) {
8 if (!wordSet.contains(word.substring(0, i))) {
9 complete = false;
10 break;
11 }
12 }
13 if (complete) {
14 if (best == null || word.length() > best.length() || (word.length() == best.length() && word.compareTo(best) < 0)) {
15 best = word;
16 }
17 }
18 }
19 return best != null ? best : "None";
20 }
21}Optimal — Trie DFS Through Complete Prefix Chains
OptimalInsert every word into a trie, marking isEnd wherever a word actually finishes. Then explore the trie from the root, stepping only into a child whose own isEnd is true — that's the same condition as before: "this next prefix is itself a previously inserted word." Any real word the walk reaches (never the empty root path itself) is automatically a complete chain. Track the best one seen; if the walk never reaches anywhere, nothing was complete, so report "None."
O(N)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 private String best;
8
9 private void dfs(TrieNode node, StringBuilder path) {
10 if (path.length() > 0 && (best == null || path.length() > best.length() || (path.length() == best.length() && path.toString().compareTo(best) < 0))) {
11 best = path.toString();
12 }
13 for (int i = 0; i < 26; i++) {
14 TrieNode child = node.children[i];
15 if (child != null && child.isEnd) {
16 path.append((char) ('a' + i));
17 dfs(child, path);
18 path.deleteCharAt(path.length() - 1);
19 }
20 }
21 }
22
23 public String longestCompleteString(String[] words) {
24 best = null;
25 TrieNode root = new TrieNode();
26 for (String word : words) {
27 TrieNode node = root;
28 for (char c : word.toCharArray()) {
29 int idx = c - 'a';
30 if (node.children[idx] == null) {
31 node.children[idx] = new TrieNode();
32 }
33 node = node.children[idx];
34 }
35 node.isEnd = true;
36 }
37 dfs(root, new StringBuilder());
38 return best != null ? best : "None";
39 }
40}