Design Search Autocomplete System
Design Search Autocomplete System is a hard tries problem solved with the basics pattern.
The best approach, optimal (trie with a top-3 list per node), runs in O(L) per add, O(1) per character typed time and O(T) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan every sentence) up.
Problem
Build the suggestion box of a search bar. It starts with a history of past searches: sentences[i] was searched times[i] times. Then the user types one character at a time through input(c).
- If
cis a letter or a space, it extends the sentence being typed. Return the three most popular past sentences that start with everything typed so far, most searched first; sentences with the same count are ordered alphabetically (character codes, so a space comes before any letter). Return fewer if fewer match. - If
cis'#', the user has finished the current sentence: record it as searched one more time (adding it to the history if it is new), start a fresh sentence, and return an empty list.
Implement the class AutocompleteSystem with the constructor AutocompleteSystem(String[] sentences, int[] times) and the method List<String> input(char c).
Examples
Example 1
- Input
AutocompleteSystem(["code red", "coffee", "cold", "cola", "comet"], [3, 5, 2, 2, 1]); input('c'); input('o'); input('l'); input('d'); input('#'); input('c')- Output
["coffee", "code red", "cola"], ["coffee", "code red", "cola"], ["cola", "cold"], ["cold"], [], ["coffee", "code red", "cold"]- Why
- cola and cold are tied at 2, so cola wins alphabetically. Pressing # saves cold as searched once more, raising it to 3, which ties code red; code red sorts first.
Example 2
- Input
AutocompleteSystem(["go home", "go"], [1, 1]); input('g'); input('o'); input(' '); input('x'); input('#'); input('g')- Output
["go", "go home"], ["go", "go home"], ["go home"], [], [], ["go", "go home", "go x"]- Why
- Spaces are part of the prefix. go x matches nothing while typed, but after # it is a new sentence with count 1.
Constraints
1 <= sentences.length <= 100,sentences.length == times.length,1 <= times[i] <= 50.1 <= sentences[i].length <= 100; sentences use lowercase English letters and spaces, and are distinct.cis a lowercase letter, a space' ', or'#';'#'is never the first character of a sentence being typed.- Each typed sentence has at most 200 characters, and there are at most
5000calls toinput.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan every sentence) | O(N · L + N log N) per call | O(N · L) |
| Optimal (trie with a top-3 list per node) | O(L) per add, O(1) per character typed | O(T) |
1Brute force (scan every sentence)
O(N · L + N log N) per callEach call checks all N stored sentences (prefix check up to L characters) and sorts the matches.O(N · L)The map stores every sentence.Store counts in a hash map and the typed text in a builder. On each character, scan every stored sentence, keep those that start with the typed text, sort them by count (high first) then alphabetically, and return the first three. On #, add 1 to the typed sentence's count and reset.
- Constructor: count[sentences[i]] += times[i].
- input('#'): count[typed] += 1, clear typed, return [].
- Otherwise append c to typed, collect sentences with prefix typed, sort by (-count, sentence), return the first three.
class AutocompleteSystem {
private final Map<String, Integer> count = new HashMap<>();
private final StringBuilder typed = new StringBuilder();
public AutocompleteSystem(String[] sentences, int[] times) {
for (int i = 0; i < sentences.length; i++) count.merge(sentences[i], times[i], Integer::sum);
}
public List<String> input(char c) {
if (c == '#') {
count.merge(typed.toString(), 1, Integer::sum);
typed.setLength(0);
return new ArrayList<>();
}
typed.append(c);
String prefix = typed.toString();
List<String> matches = new ArrayList<>();
for (String s : count.keySet())
if (s.startsWith(prefix)) matches.add(s);
matches.sort((a, b) -> {
int ca = count.get(a), cb = count.get(b);
return ca != cb ? cb - ca : a.compareTo(b);
});
return new ArrayList<>(matches.subList(0, Math.min(3, matches.size())));
}
}class AutocompleteSystem:
def __init__(self, sentences: List[str], times: List[int]):
self.count = defaultdict(int)
for s, t in zip(sentences, times):
self.count[s] += t
self.typed = []
def input(self, c: str) -> List[str]:
if c == '#':
self.count[''.join(self.typed)] += 1
self.typed = []
return []
self.typed.append(c)
prefix = ''.join(self.typed)
matches = [s for s in self.count if s.startswith(prefix)]
matches.sort(key=lambda s: (-self.count[s], s))
return matches[:3]class AutocompleteSystem {
unordered_map<string, int> count;
string typed;
public:
AutocompleteSystem(vector<string> sentences, vector<int> times) {
for (size_t i = 0; i < sentences.size(); i++) count[sentences[i]] += times[i];
}
vector<string> input(char c) {
if (c == '#') {
count[typed] += 1;
typed.clear();
return {};
}
typed += c;
vector<string> matches;
for (auto& [s, k] : count)
if (s.compare(0, typed.size(), typed) == 0) matches.push_back(s);
sort(matches.begin(), matches.end(), [&](const string& a, const string& b) {
int ca = count[a], cb = count[b];
return ca != cb ? ca > cb : a < b;
});
if (matches.size() > 3) matches.resize(3);
return matches;
}
};class AutocompleteSystem {
constructor(sentences, times) {
this.count = new Map();
for (let i = 0; i < sentences.length; i++)
this.count.set(sentences[i], (this.count.get(sentences[i]) || 0) + times[i]);
this.typed = '';
}
input(c) {
if (c === '#') {
this.count.set(this.typed, (this.count.get(this.typed) || 0) + 1);
this.typed = '';
return [];
}
this.typed += c;
const matches = [];
for (const s of this.count.keys())
if (s.startsWith(this.typed)) matches.push(s);
matches.sort((a, b) => {
const ca = this.count.get(a), cb = this.count.get(b);
if (ca !== cb) return cb - ca;
return a < b ? -1 : a > b ? 1 : 0;
});
return matches.slice(0, 3);
}
}2Optimal (trie with a top-3 list per node)
O(L) per add, O(1) per character typedA sentence update touches L nodes and sorts a list of at most four at each; a query moves one step and copies at most three strings.O(T)T = total characters stored in the trie; each node also holds up to three references.Build a trie over the sentences. Every node keeps the (at most) three best sentences that pass through it. When a sentence's count grows, walk its path and, at each node, put the sentence in that node's list if it is missing, re-sort the short list and cut it back to three. Because counts only grow, a sentence can only enter a node's top three at the moment its own count changes, so these lists stay correct. Queries keep a pointer to the node of the current prefix and just read its list.
- add(s, k): count[s] += k; walk s through the trie creating nodes; at each node, add s to node.top if absent, sort by (-count, sentence), drop anything past the third.
- Constructor: add(sentences[i], times[i]).
- input(c): on '#', add(typed, 1), clear typed, reset the pointer to the root and return [].
- Otherwise append c; move the pointer to its child for c (null stays null once a prefix has no matches); return a copy of pointer.top, or [] for null.
class AutocompleteSystem {
private static class Node {
Node[] next = new Node[27];
List<String> top = new ArrayList<>();
}
private final Node root = new Node();
private final Map<String, Integer> count = new HashMap<>();
private final StringBuilder typed = new StringBuilder();
private Node cur = root;
public AutocompleteSystem(String[] sentences, int[] times) {
for (int i = 0; i < sentences.length; i++) add(sentences[i], times[i]);
}
public List<String> input(char c) {
if (c == '#') {
add(typed.toString(), 1);
typed.setLength(0);
cur = root;
return new ArrayList<>();
}
typed.append(c);
if (cur != null) cur = cur.next[index(c)];
return cur == null ? new ArrayList<>() : new ArrayList<>(cur.top);
}
private int index(char c) {
return c == ' ' ? 26 : c - 'a';
}
private void add(String s, int k) {
count.merge(s, k, Integer::sum);
Node node = root;
for (int i = 0; i < s.length(); i++) {
int j = index(s.charAt(i));
if (node.next[j] == null) node.next[j] = new Node();
node = node.next[j];
if (!node.top.contains(s)) node.top.add(s);
node.top.sort((a, b) -> {
int ca = count.get(a), cb = count.get(b);
return ca != cb ? cb - ca : a.compareTo(b);
});
if (node.top.size() > 3) node.top.remove(3);
}
}
}class TrieNode:
def __init__(self):
self.next = {}
self.top = []
class AutocompleteSystem:
def __init__(self, sentences: List[str], times: List[int]):
self.root = TrieNode()
self.count = defaultdict(int)
self.typed = []
self.cur = self.root
for s, t in zip(sentences, times):
self.add(s, t)
def input(self, c: str) -> List[str]:
if c == '#':
self.add(''.join(self.typed), 1)
self.typed = []
self.cur = self.root
return []
self.typed.append(c)
if self.cur is not None:
self.cur = self.cur.next.get(c)
return list(self.cur.top) if self.cur is not None else []
def add(self, s: str, k: int) -> None:
self.count[s] += k
node = self.root
for ch in s:
if ch not in node.next:
node.next[ch] = TrieNode()
node = node.next[ch]
if s not in node.top:
node.top.append(s)
node.top.sort(key=lambda x: (-self.count[x], x))
del node.top[3:]class AutocompleteSystem {
struct Node {
Node* next[27] = {};
vector<string> top;
};
Node* root = new Node();
Node* cur;
unordered_map<string, int> count;
string typed;
static int index(char c) { return c == ' ' ? 26 : c - 'a'; }
void add(const string& s, int k) {
count[s] += k;
Node* node = root;
for (char ch : s) {
int j = index(ch);
if (!node->next[j]) node->next[j] = new Node();
node = node->next[j];
if (find(node->top.begin(), node->top.end(), s) == node->top.end()) node->top.push_back(s);
sort(node->top.begin(), node->top.end(), [&](const string& a, const string& b) {
int ca = count[a], cb = count[b];
return ca != cb ? ca > cb : a < b;
});
if (node->top.size() > 3) node->top.resize(3);
}
}
public:
AutocompleteSystem(vector<string> sentences, vector<int> times) {
cur = root;
for (size_t i = 0; i < sentences.size(); i++) add(sentences[i], times[i]);
}
vector<string> input(char c) {
if (c == '#') {
add(typed, 1);
typed.clear();
cur = root;
return {};
}
typed += c;
if (cur) cur = cur->next[index(c)];
return cur ? cur->top : vector<string>();
}
};class AutocompleteSystem {
constructor(sentences, times) {
this.root = { next: new Map(), top: [] };
this.count = new Map();
this.typed = '';
this.cur = this.root;
for (let i = 0; i < sentences.length; i++) this.add(sentences[i], times[i]);
}
input(c) {
if (c === '#') {
this.add(this.typed, 1);
this.typed = '';
this.cur = this.root;
return [];
}
this.typed += c;
if (this.cur !== null) this.cur = this.cur.next.get(c) || null;
return this.cur === null ? [] : this.cur.top.slice();
}
add(s, k) {
this.count.set(s, (this.count.get(s) || 0) + k);
let node = this.root;
for (const ch of s) {
if (!node.next.has(ch)) node.next.set(ch, { next: new Map(), top: [] });
node = node.next.get(ch);
if (!node.top.includes(s)) node.top.push(s);
node.top.sort((a, b) => {
const ca = this.count.get(a), cb = this.count.get(b);
if (ca !== cb) return cb - ca;
return a < b ? -1 : a > b ? 1 : 0;
});
if (node.top.length > 3) node.top.length = 3;
}
}
}Edge cases to test
- A prefix that matches nothing (and stays empty for the rest of the sentence)
- Fewer than three matches
- Ties in count, broken alphabetically (a space sorts before every letter)
- A typed sentence that already exists, which raises its count
- A sentence that is a prefix of another, like go and go home
Hints
Hint 1
Keep a map from sentence to count. For a query, every sentence that starts with the typed prefix is a candidate; sort them by (-count, sentence) and take three.
Hint 2
A trie makes the prefix part cheap: keep a pointer to the trie node of the current prefix and move it one character per call.
Hint 3
Counts only ever grow, and only for the sentence being saved. So each trie node can store its own top-3 list and refresh it only along the path of the sentence whose count changed.
FAQ
What is the best time complexity for Design Search Autocomplete System?
Optimal (trie with a top-3 list per node) runs in O(L) per add, O(1) per character typed time and O(T) extra space. A sentence update touches L nodes and sorts a list of at most four at each; a query moves one step and copies at most three strings.
Which pattern does Design Search Autocomplete System use?
It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design In-Memory File System.
Is there a brute force solution for Design Search Autocomplete System?
Yes. Brute force (scan every sentence) takes O(N · L + N log N) per call time and O(N · L) space. Store counts in a hash map and the typed text in a builder.
Which edge cases should I test for Design Search Autocomplete System?
A prefix that matches nothing (and stays empty for the rest of the sentence); Fewer than three matches; Ties in count, broken alphabetically (a space sorts before every letter); A typed sentence that already exists, which raises its count; A sentence that is a prefix of another, like go and go home.