Autocomplete With Frequencies

Design a class Autocomplete that ranks phrases by how often they were used:

• Autocomplete(phrases, counts): phrases[i] was used counts[i] times so far (phrases distinct).
• record(phrase) adds one more use of phrase (a new phrase starts at 1).
• suggest(prefix) returns up to 3 stored phrases starting with prefix, ordered by count descending, ties broken by lexicographic (ASCII) order. suggest("") ranks all phrases.

Examples

ops:  ["Autocomplete", "suggest", "record", "suggest", "suggest"]
args: [[["good morning", "goodbye", "go for it", "good night"], [4, 2, 3, 1]], ["go"], ["go for it"], ["go"], ["x"]]
Output: [None, ["good morning", "go for it", "goodbye"], None, ["go for it", "good morning", "goodbye"], []]
Explanation: after record("go for it") its count is 4, tied with "good morning"; "go for it" is smaller.

Constraints

• Phrases are lowercase letters and spaces, length <= 100; up to 5000 calls in total
• Target: record in O(len(phrase)); suggest in O(len(prefix) + m) where m is the number of phrases with that prefix (do not scan every stored phrase)

Goals

• Attach the set of completions to every trie node
• Rank suggestions by a frequency that changes over time