Counter: top n-grams with deterministic ties

Tally the word n-grams of a document and return the k most frequent, with a tie-break that does not depend on the order the text happened to arrive in.

def solve(text: str, n: int, k: int) -> list[tuple[str, int]]:

• An n-gram is n consecutive whitespace-separated words, joined by a single space. "the cat sat" with n = 2 yields "the cat" and "cat sat".
• Split on arbitrary runs of whitespace — str.split() with no argument already does exactly this.
• Return (ngram, count) pairs sorted by count descending, then n-gram ascending. Return at most k of them.
• If n < 1 or k < 1, return []. If the text has fewer than n words, there are no n-grams, so return [].

Why the explicit tie-break is the point. Counter.most_common(k) breaks ties by first-seen order, because Counter is a dict and dict preserves insertion order. That makes your “top 10” a function of the order the input arrived in — fine until the input comes from a set, a os.listdir, a thread pool, or a query without an ORDER BY, at which point your report changes between runs and nobody can tell whether the data moved or the code did. A report a human will diff needs a total order.

Why you still want Counter. most_common(k) is heapq.nlargest underneath — $O(n \log k)$, not a full sort. Here you re-sort anyway to fix the tie-break, but the counting itself is one C-level pass rather than a Python loop with a membership test per element.

Your submission must pass mypy --strict. Counter is generic in its element type — a bare Counter annotation is a type-arg error under --disallow-any-generics, so write Counter[str].

Returns a list of tuples, not a list of lists. The harness compares container types exactly.