Most Common N-Grams
Learn this problem
xAIFULLTIMEPHONE SCREENProblem statement
A document is represented as whitespace-separated tokens. Split document on one or more whitespace characters, discard empty pieces, and preserve every remaining token exactly, including case and punctuation.
For each value n = lengths[i], consider every contiguous sequence of n tokens. Return the sequence that occurs most often, joined with single spaces. If several sequences have the same maximum frequency, return the one whose first occurrence starts earliest in the document. If n exceeds the token count, return the empty string for that request.
Return one result for each entry of lengths, in the same order. Duplicate requested lengths must produce duplicate results.
Function
mostCommonNGrams(document: String, lengths: int[]) → String[]Examples
Example 1
document = "a b a b a c"lengths = [1,2,3,7]return = ["a","a b","a b a",""]a is the most common token. The bigrams a b and b a both occur twice, so the earlier first occurrence selects a b. The trigram a b a occurs twice.
Example 2
document = "Red fish red fish"lengths = [1,2]return = ["fish","Red fish"]Token matching is case-sensitive, so fish occurs twice while Red and red are distinct. All bigrams tie, selecting the first one, Red fish.
Constraints
1 <= document.length() <= 200000.- The document contains at least one non-whitespace token.
1 <= lengths.length <= 100.1 <= lengths[i] <= 1000.- Across distinct requested lengths, the sum of
n * (tokenCount - n + 1)for everyn <= tokenCountis at most1000000.