Most-Frequent Next-Word Predictor

Train a next-word predictor from one ordered array of case-sensitive tokens. Every adjacent pair contributes one observation from its first token to its second.
For each query token, return the observed following token with highest frequency. Break frequency ties by lexicographically smaller token. Return the empty string when the query has no observed successor. Precompute the winning successor while processing the training data so each query is answered in average O(1) time.

Function
predictNextWords(trainingTokens: String[], queries: String[]) → String[]

Examples
Example 1
trainingTokens = ["i","like","tea","i","like","coffee","i","like","tea"]
queries = ["i","like"]
return = ["like","tea"]
The word after i is always like, while tea follows like twice and coffee once.
Example 2
trainingTokens = ["x","z","x","a"]
queries = ["x"]
return = ["a"]
The successors a and z tie, so the lexicographically smaller a wins.

Constraints
1 <= trainingTokens.length, queries.length <= 200000
Every token is a nonempty printable ASCII string of length at most 40.
The total number of token characters across both arrays is at most 1000000.

The trick is a map of maps. Outer key is the first token, inner map counts each successor. Walk the array once, bump count for pair (t[i], t[i+1]). While you update, track the current best successor for that first token: if the new count beats the best count, or ties it and the token is lexicographically smaller, replace it. Store the winner in a third map so each query is a single lookup, returning the empty string on a miss. The pitfall is updating the winner wrongly on ties. A token whose count rises can only beat the winner by being higher, or equal and smaller, so check both. Also, a single-token training array has zero pairs, so every query returns empty. Tokens are case-sensitive, so never lowercase anything. Don't scan the inner map per query, that blows the time budget. If the tie logic slips under pressure, StealthCoder is your hedge during the live OA.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.