> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Design Search Autocomplete System

> Tested Python solution for LeetCode 642 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 642, [Hard](/catalog/hard). Topics: [Depth-First Search](/catalog/topics/depth-first-search), [Design](/catalog/topics/design), [Trie](/catalog/topics/trie), [String](/catalog/topics/string), [Data Stream](/catalog/topics/data-stream), [Sorting](/catalog/topics/sorting), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/design-search-autocomplete-system/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 642   # by problem number
lcpy gen -s design_search_autocomplete_system   # by problem name
```

## Problem

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character `'#'`).

You are given a string array `sentences` and an integer array `times` both of length `n` where `sentences[i]` is a previously typed sentence and `times[i]` is the corresponding number of times the sentence was typed. For each input character except `'#'`, return the top `3` historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:

* The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
* The returned top `3` hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
* If less than `3` hot sentences exist, return as many as you can.
* When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Implement the `AutocompleteSystem` class:

* `AutocompleteSystem(String[] sentences, int[] times)` Initializes the object with the `sentences` and `times` arrays.
* `List<String> input(char c)` This indicates that the user typed the character `c`.
  * Returns an empty array `[]` if `c == '#'` and stores the inputted sentence in the system.
  * Returns the top `3` historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than `3` matches, return them all.

### Examples

```
Input
["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output
[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]

Explanation
AutocompleteSystem obj = new AutocompleteSystem([...], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]
obj.input(" "); // return ["i love you", "i love leetcode"]
obj.input("a"); // return []
obj.input("#"); // return []
```

### Constraints

* `n == sentences.length`
* `n == times.length`
* `1 <= n <= 100`
* `1 <= sentences[i].length <= 100`
* `1 <= times[i] <= 50`
* `c` is a lowercase English letter, a hash `'#'`, or space `' '`.
* Each tested sentence will be a sequence of characters `c` that end with the character `'#'`.
* Each tested sentence will have a length in the range `[1, 200]`.
* The words in each input sentence are separated by single spaces.
* At most `5000` calls will be made to `input`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_search_autocomplete_system/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_search_autocomplete_system/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class AutocompleteSystem:
    # Time: input O(n * L + n log n) per call with n = sentence count
    # Space: O(total sentence length)
    def __init__(self, sentences: list[str], times: list[int]) -> None:
        self.counts: dict[str, int] = dict(zip(sentences, times, strict=True))
        self.buffer = ""

    def input(self, c: str) -> list[str]:
        if c == "#":
            if self.buffer:
                self.counts[self.buffer] = self.counts.get(self.buffer, 0) + 1
            self.buffer = ""
            return []
        self.buffer += c
        matches = [s for s in self.counts if s.startswith(self.buffer)]
        matches.sort(key=lambda s: (-self.counts[s], s))
        return matches[:3]
```

## Complexity

| Time | Space |
| - | - |
| input O(n \* L + n log n) per call with n = sentence count | O(total sentence length) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.