OA: Search box suggestions

A search box shows up to three suggestions while the user types. Suggestions come from what people searched before: phrases searched more often come first.

Build SearchBox:

• SearchBox() starts with no history.
• record(phrase) -> int: someone searched for phrase; add one to its count and return the new count.
• count(phrase) -> int: how many times phrase has been searched (0 if never).
• suggest(prefix) -> list[str]: up to 3 recorded phrases that start with prefix, highest count first. Equal counts are ordered alphabetically by ordinary string comparison (a space sorts before every letter). The empty prefix matches every phrase. Return [] if nothing matches.

sb = SearchBox()
sb.record("cat food")    # 1
sb.record("car wash")    # 1
sb.record("cat food")    # 2
sb.record("cart")        # 1
sb.record("dog")         # 1
sb.suggest("ca")         # ["cat food", "car wash", "cart"]
sb.suggest("car")        # ["car wash", "cart"]
sb.suggest("")           # ["cat food", "car wash", "cart"]   ("dog" also has 1, but sorts last)
sb.suggest("x")          # []
sb.count("cat food")     # 2
sb.count("cat")          # 0   (only a prefix of a phrase)

Phrases have 1 to 30 characters from a-z and space; prefixes have 0 to 30. At this level there are at most a few thousand calls, so any clear approach is fine. Later levels add bulk updates, much larger histories and deletions, so keep the ranking rule in one place.