# Implement a Stateful Search Autocomplete Session Build an autocomplete engine from historical sentences and their usage counts. While a user types a session, return up to three historical sentences that begin with the current prefix. Rank candidates by descending usage count, breaking ties by lexicographically smaller sentence. The order of the initial `sentences` input must not affect the result. The character `#` ends the current sentence. Commit the nonempty accumulated text with one additional use, return an empty suggestion list for that character, and reset the prefix for a new session. ## Function Contract ```python def run_autocomplete( sentences: list[str], frequencies: list[int], keystrokes: str, ) -> list[list[str]]: ... ``` Return one suggestion list for each character in `keystrokes`. ## Constraints - `len(sentences) == len(frequencies)` - Initial sentences are distinct and nonempty. - Sentences and typed characters contain lowercase English letters and spaces; `#` appears only in `keystrokes`. - `1 <= frequencies[i] <= 10**6` - At most 500 initial sentences and 500 keystrokes are supplied. - If `#` is entered with an empty prefix, do not add an empty sentence. ## Example ```text sentences = ["island", "ironman", "i love you", "i love leetcode"] frequencies = [3, 2, 5, 2] keystrokes = "i a#i" ``` The function returns a list of suggestions after each character, including an empty list at `#`, and the newly committed sentence participates in later prefixes.