Complete String (All Prefixes Exist)
Description
You are given an array of strings A of size N. Each element is a non-empty string consisting of lowercase English letters.
A string is called a complete string if every prefix of that string is also present in the array A. For example, if the string is "abc", then "a", "ab", and "abc" must all exist somewhere in the array for it to be complete.
Your task is to find the longest complete string in the array. If there are multiple complete strings with the same maximum length, return the lexicographically smallest one. If no complete string exists at all, return "None".
Note: String P is lexicographically smaller than string Q if there exists some index i such that for all j < i, P[j] == Q[j] and P[i] < Q[i]. Also, if P is a prefix of Q, then P is considered lexicographically smaller (e.g., "code" < "coder").
Examples
Example 1
Input: N = 6, A = ["n", "ni", "nin", "ninj", "ninja", "ninga"]
Output: "ninja"
Explanation:
- "ninja" has prefixes: "n", "ni", "nin", "ninj", "ninja". All five are present in the array. So "ninja" is a complete string of length 5.
- "ninga" has prefixes: "n", "ni", "nin", "ning", "ninga". The prefix "ning" is NOT present in the array. So "ninga" is NOT a complete string.
- Among all complete strings ("n", "ni", "nin", "ninj", "ninja"), the longest is "ninja" with length 5.
Example 2
Input: N = 2, A = ["ab", "bc"]
Output: "None"
Explanation:
- "ab" has prefix "a", which is NOT present in the array. So "ab" is not complete.
- "bc" has prefix "b", which is NOT present in the array. So "bc" is not complete.
- No complete string exists, so the answer is "None".
Example 3
Input: N = 4, A = ["ab", "abc", "a", "bp"]
Output: "abc"
Explanation:
- "a" has only the prefix "a" (itself), which is present. Complete string of length 1.
- "ab" has prefixes "a" and "ab", both present. Complete string of length 2.
- "abc" has prefixes "a", "ab", and "abc", all present. Complete string of length 3.
- "bp" has prefix "b", which is NOT present. Not complete.
- The longest complete string is "abc" with length 3.
Constraints
- 1 ≤ N ≤ 10⁵
- 1 ≤ |A[i]| ≤ 10⁵
- A[i] consists of lowercase English letters only
- Sum of |A[i]| over all strings ≤ 10⁵
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem: for each string in the array, extract every one of its prefixes and then check whether that prefix exists somewhere in the array by scanning through all strings.
Imagine you have a list of words written on index cards. You pick up one card, say the word is "ninja". You need to verify that "n", "ni", "nin", "ninj", and "ninja" each appear on some card in the pile. To check each prefix, you flip through the entire pile of cards looking for a match. If every prefix is found, the word is "complete".
You repeat this for every card, keeping track of the longest complete word you have found so far. If two words have the same length, you prefer the one that comes first alphabetically.
Step-by-Step Explanation
Let's trace through a small example:
A = ["ab", "abc", "a", "bp"]
Step 1: Check word "ab" (length 2).
- Prefix "a" (length 1): scan array → found "a" at index 2 ✓
- Prefix "ab" (length 2): scan array → found "ab" at index 0 ✓
- All prefixes found! "ab" is complete. result = "ab" (length 2).
Step 2: Check word "abc" (length 3).
- Prefix "a": scan array → found at index 2 ✓
- Prefix "ab": scan array → found at index 0 ✓
- Prefix "abc": scan array → found at index 1 ✓
- All prefixes found! "abc" is complete. Length 3 > 2 → update result = "abc".
Step 3: Check word "a" (length 1).
- Prefix "a": scan array → found at index 2 ✓
- Complete, but length 1 < 3 → result stays "abc".
Step 4: Check word "bp" (length 2).
- Prefix "b": scan array → not found in any element ✗
- Not complete. Skip.
Result: "abc".
Algorithm
- Initialize
result = "None". - For each string
wordin the arrayA:
a. SetisComplete = true.
b. For each prefix lengthlenfrom 1 to|word|:- Extract prefix
p = word[0..len-1]. - Scan the entire array
Ato check if any element equalsp. - If
pis not found, setisComplete = falseand break.
c. IfisCompleteis true: - If
result == "None", or|word| > |result|, or (|word| == |result|andword < resultlexicographically): updateresult = word.
- Extract prefix
- Return
result.
Code
#include <vector>
#include <string>
using namespace std;
string completeString(int n, vector<string>& a) {
string result = "None";
for (int i = 0; i < n; i++) {
bool isComplete = true;
for (int len = 1; len <= (int)a[i].size(); len++) {
string prefix = a[i].substr(0, len);
bool found = false;
for (int j = 0; j < n; j++) {
if (a[j] == prefix) {
found = true;
break;
}
}
if (!found) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result == "None" || a[i].size() > result.size() ||
(a[i].size() == result.size() && a[i] < result)) {
result = a[i];
}
}
}
return result;
}def completeString(n: int, a: list[str]) -> str:
result = "None"
for word in a:
is_complete = True
for length in range(1, len(word) + 1):
prefix = word[:length]
found = any(other == prefix for other in a)
if not found:
is_complete = False
break
if is_complete:
if result == "None" or len(word) > len(result) or \
(len(word) == len(result) and word < result):
result = word
return resultpublic class Solution {
public static String completeString(int n, String[] a) {
String result = "None";
for (int i = 0; i < n; i++) {
boolean isComplete = true;
for (int len = 1; len <= a[i].length(); len++) {
String prefix = a[i].substring(0, len);
boolean found = false;
for (int j = 0; j < n; j++) {
if (a[j].equals(prefix)) {
found = true;
break;
}
}
if (!found) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result.equals("None") || a[i].length() > result.length() ||
(a[i].length() == result.length() && a[i].compareTo(result) < 0)) {
result = a[i];
}
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(N² × L²)
For each of the N strings (with maximum length L), we check up to L prefixes. For each prefix, we scan the entire array of N strings, and each string comparison costs up to O(L). This gives O(N × L × N × L) = O(N² × L²).
With N up to 10⁵ and total characters up to 10⁵, this could reach around 10¹⁰ operations in worst-case scenarios — far too slow for the given time limit.
Space Complexity: O(L)
We only need space for the current prefix substring (at most length L). No additional data structures that grow with input size.
Why This Approach Is Not Efficient
The brute force approach is extremely slow because for every prefix of every string, it scans the entire array. This leads to O(N² × L²) time, which for the given constraints (N up to 10⁵, total characters up to 10⁵) would be catastrophically slow.
The core redundancy: we repeatedly scan the same array searching for the same strings. When checking "ninja", we scan the array for "n", then scan again for "ni", then again for "nin" — each time doing O(N) work that could be avoided.
Key insight: If we put all strings into a HashSet first, we can check whether any prefix exists in O(|prefix|) average time (for computing the hash) instead of O(N × L) time (for linear scanning). This eliminates the inner O(N) scan entirely.
Better Approach - HashSet
Intuition
Instead of scanning the entire array every time we want to check if a prefix exists, we can store all strings in a HashSet (an unordered set). A HashSet supports average O(1) lookups by key, which means checking if a prefix exists becomes nearly instant — no more scanning.
The algorithm is simple: first, dump all strings from the array into a set. Then for each string, generate every prefix and look it up in the set. If all prefixes are found, the string is complete.
Think of it like this: instead of flipping through the entire pile of index cards every time, you first organize all the cards into alphabetical folders (the hash set). Now when you need to check if "nin" exists, you go directly to the right folder and find it immediately.
Step-by-Step Explanation
Let's trace with A = ["n", "ni", "nin", "ninj", "ninja", "ninga"]:
Step 1: Build HashSet containing all 6 words: {"n", "ni", "nin", "ninj", "ninja", "ninga"}.
Step 2: Check word "n". Only prefix is "n" → look up in set → found ✓. Complete! result = "n" (length 1).
Step 3: Check word "ni". Prefix "n" → found ✓. Prefix "ni" → found ✓. Complete! Length 2 > 1, update result = "ni".
Step 4: Check word "nin". Prefixes "n" ✓, "ni" ✓, "nin" ✓. Complete! result = "nin" (length 3).
Step 5: Check word "ninj". Prefixes "n" ✓, "ni" ✓, "nin" ✓, "ninj" ✓. Complete! result = "ninj" (length 4).
Step 6: Check word "ninja". Prefixes "n" ✓, "ni" ✓, "nin" ✓, "ninj" ✓, "ninja" ✓. Complete! result = "ninja" (length 5).
Step 7: Check word "ninga". Prefixes: "n" ✓, "ni" ✓, "nin" ✓, "ning" → look up in set → NOT found ✗. Not complete! The prefix "ning" was never added to the array.
Step 8: All words checked. Result: "ninja" (length 5).
HashSet Prefix Checking — Finding Complete Strings — Watch how we use a HashSet for fast prefix lookups, checking each word's prefixes to determine if it is a complete string.
Algorithm
- Insert all strings from array
Ainto a HashSetwordSet. - Initialize
result = "None". - For each string
wordinA:
a. SetisComplete = true.
b. For each prefix lengthlenfrom 1 to|word|:- Create the substring
prefix = word[0..len-1]. - If
prefixis NOT inwordSet, setisComplete = falseand break.
c. IfisCompleteis true: - Update
resultifwordis longer, or same length but lexicographically smaller.
- Create the substring
- Return
result.
Code
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
string completeString(int n, vector<string>& a) {
unordered_set<string> wordSet(a.begin(), a.end());
string result = "None";
for (const string& word : a) {
bool isComplete = true;
for (int len = 1; len <= (int)word.size(); len++) {
if (wordSet.find(word.substr(0, len)) == wordSet.end()) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result == "None" || word.size() > result.size() ||
(word.size() == result.size() && word < result)) {
result = word;
}
}
}
return result;
}def completeString(n: int, a: list[str]) -> str:
word_set = set(a)
result = "None"
for word in a:
is_complete = True
for length in range(1, len(word) + 1):
if word[:length] not in word_set:
is_complete = False
break
if is_complete:
if result == "None" or len(word) > len(result) or \
(len(word) == len(result) and word < result):
result = word
return resultimport java.util.*;
public class Solution {
public static String completeString(int n, String[] a) {
Set<String> wordSet = new HashSet<>(Arrays.asList(a));
String result = "None";
for (String word : a) {
boolean isComplete = true;
for (int len = 1; len <= word.length(); len++) {
if (!wordSet.contains(word.substring(0, len))) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result.equals("None") || word.length() > result.length() ||
(word.length() == result.length() && word.compareTo(result) < 0)) {
result = word;
}
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(∑|A[i]|²) — simplifies to O(N × L²) in the worst case
Building the HashSet takes O(total characters). For each string of length l, we generate l prefixes of lengths 1, 2, …, l. Creating each prefix substring costs O(k) for length k, and hashing it also costs O(k). So per string: O(1 + 2 + … + l) = O(l²). Across all strings, the total is O(∑ l_i²). In the worst case where one string has length L, this is O(L²) for that string.
This is significantly faster than brute force because we eliminated the O(N) scan for each prefix check. But the O(l²) per string cost due to substring creation and hashing is still a bottleneck.
Space Complexity: O(total characters)
The HashSet stores all N strings, consuming space proportional to the total number of characters across all strings.
Why This Approach Is Not Efficient
The HashSet approach eliminated the O(N) scan per prefix check, but it introduced a different bottleneck: substring creation and hashing.
For a string of length l, we create l prefix substrings of lengths 1, 2, …, l. Each substring must be allocated in memory and then hashed character by character. The total cost for one string is O(1 + 2 + … + l) = O(l²). If one string has length 10⁵, that's 10¹⁰ ÷ 2 ≈ 5 × 10⁹ operations just for that one string — too slow.
Key insight: A Trie (prefix tree) is a data structure purpose-built for prefix queries. If we insert all strings into a Trie, then for any string we can walk the Trie character by character — at each step, we simply check whether the current node is marked as an end-of-word. This takes exactly O(l) per string, with no substring creation and no hashing. The Trie naturally shares common prefixes, making it both time-efficient and space-efficient.
Optimal Approach - Trie
Intuition
A Trie (pronounced "try") is a tree-like data structure where each node represents a character, and paths from the root to nodes spell out strings. Nodes can be marked as "end-of-word" to indicate that the path from the root to that node forms a complete word in our dictionary.
The key insight is that a Trie naturally represents all prefixes. When we insert the word "ninja" into a Trie, we create nodes for 'n', 'i', 'n', 'j', 'a'. If we also insert "n", "ni", "nin", and "ninj" separately, each of those intermediate nodes gets marked as end-of-word.
To check if "ninja" is a complete string, we simply walk the Trie along the path n → i → n → j → a. At each node we visit, we check: "Is this node marked as end-of-word?" If YES at every step, the word is complete. If we encounter any node that is NOT end-of-word, some prefix is missing from the array, and the word is not complete.
This avoids creating any substring objects. We walk one character at a time, checking a boolean flag — O(l) total work for a string of length l.
Step-by-Step Explanation
Let's trace with A = ["n", "ni", "nin", "ninj", "ninja", "ninga"]:
Phase 1: Build the Trie
Step 1: Start with an empty Trie (just the root node).
Step 2: Insert "n". Create node 'n' under root. Mark 'n' as end-of-word.
Step 3: Insert "ni". Walk to existing 'n', create node 'i' under it. Mark 'i' as end-of-word.
Step 4: Insert "nin". Walk n → i, create node 'n₂' under 'i'. Mark 'n₂' as end-of-word.
Step 5: Insert "ninj". Walk n → i → n₂, create 'j'. Mark 'j' as end-of-word.
Step 6: Insert "ninja". Walk n → i → n₂ → j, create 'a'. Mark 'a' as end-of-word.
Step 7: Insert "ninga". Walk n → i → n₂, create NEW branch 'g' (not end-of-word!), then 'a₂' under 'g'. Mark 'a₂' as end-of-word. Note: 'g' is NOT marked as end-of-word because "ning" is not in the array.
Phase 2: Check Each Word
Step 8: Begin checking words for completeness. Start with "ninja".
Step 9: Walk 'n': arrive at node 'n'. Is end-of-word? YES ✓. Prefix "n" exists.
Step 10: Walk 'i': arrive at node 'ni'. Is end-of-word? YES ✓. Prefix "ni" exists.
Step 11: Walk 'n': arrive at node 'nin'. Is end-of-word? YES ✓. Prefix "nin" exists.
Step 12: Walk 'j': arrive at node 'ninj'. Is end-of-word? YES ✓. Prefix "ninj" exists.
Step 13: Walk 'a': arrive at node 'ninja'. Is end-of-word? YES ✓. ALL prefixes valid → "ninja" is COMPLETE! Update result = "ninja" (length 5).
Step 14: Check "ninga". Walk 'n'✓ → 'i'✓ → 'n'✓ → 'g': arrive at node 'ning'. Is end-of-word? NO ✗. Prefix "ning" does not exist as a word. "ninga" is NOT complete.
Step 15: All words checked. Result: "ninja" (length 5).
Trie — Insert Words and Verify Complete Strings — Watch how we build a Trie from all words, marking end-of-word nodes, then walk each word through the Trie to verify if every prefix is a complete word.
Algorithm
- Build the Trie: Create a Trie root node. For each string
wordinA:- Walk the Trie from the root, creating child nodes as needed for each character.
- Mark the final node as end-of-word.
- Initialize
result = "None". - Check each word: For each string
wordinA:
a. Walk the Trie from the root, one character at a time.
b. At each node visited, check ifisEndistrue.
c. If any node along the path hasisEnd == false, the word is NOT complete — break.
d. If all nodes haveisEnd == true, the word IS complete.
e. Updateresultif the word is longer, or same length but lexicographically smaller. - Return
result.
Code
#include <vector>
#include <string>
using namespace std;
struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() {
for (int i = 0; i < 26; i++) children[i] = nullptr;
isEnd = false;
}
};
string completeString(int n, vector<string>& a) {
TrieNode* root = new TrieNode();
// Insert all words into the Trie
for (const string& word : a) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true;
}
string result = "None";
// Check each word for completeness
for (const string& word : a) {
TrieNode* node = root;
bool isComplete = true;
for (char c : word) {
node = node->children[c - 'a'];
if (!node->isEnd) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result == "None" || word.size() > result.size() ||
(word.size() == result.size() && word < result)) {
result = word;
}
}
}
return result;
}class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def completeString(n: int, a: list[str]) -> str:
root = TrieNode()
# Insert all words into the Trie
for word in a:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
result = "None"
# Check each word for completeness
for word in a:
node = root
is_complete = True
for char in word:
node = node.children[char]
if not node.is_end:
is_complete = False
break
if is_complete:
if result == "None" or len(word) > len(result) or \
(len(word) == len(result) and word < result):
result = word
return resultclass TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}
public class Solution {
public static String completeString(int n, String[] a) {
TrieNode root = new TrieNode();
// Insert all words into the Trie
for (String word : a) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
}
node.isEnd = true;
}
String result = "None";
// Check each word for completeness
for (String word : a) {
TrieNode node = root;
boolean isComplete = true;
for (char c : word.toCharArray()) {
node = node.children[c - 'a'];
if (!node.isEnd) {
isComplete = false;
break;
}
}
if (isComplete) {
if (result.equals("None") || word.length() > result.length() ||
(word.length() == result.length() && word.compareTo(result) < 0)) {
result = word;
}
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(∑|A[i]|) — i.e., O(total characters)
Inserting all strings into the Trie costs O(total characters) since we process each character exactly once. Checking each string for completeness also costs O(total characters) — for each string of length l, we walk l nodes in the Trie doing O(1) work per node (follow a child pointer and check a boolean flag). Total: O(total characters) + O(total characters) = O(total characters).
With the constraint that total characters ≤ 10⁵, this runs in about 2 × 10⁵ operations — extremely fast.
Compared to the HashSet approach (O(∑l_i²)), the Trie avoids the quadratic cost of substring creation. For a single string of length 10⁵, the HashSet approach does ~5 × 10⁹ operations while the Trie does only 10⁵ — a 50,000× improvement.
Space Complexity: O(total characters × 26)
Each Trie node has an array of 26 child pointers. In the worst case, every character creates a new node, so we have O(total characters) nodes × 26 pointers each. In practice, shared prefixes reduce this significantly. Using a hash map for children instead of a fixed array reduces space to O(total characters) at the cost of slightly higher constant factors.