Count N-Grams and Break Ties with Counter

Find the phrases that come up most often in a piece of text. Here a phrase is an n-gram, which is n words in a row joined by single spaces. Count every n-gram, then return the k most common, with ties in alphabetical order.

solve("the cat sat on the mat the cat ran", 2, 3)
# [("the cat", 2), ("cat ran", 1), ("cat sat", 1)]

What to write

Fill in solve:

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

• Split text with text.split() and no argument. It splits on any run of spaces, tabs or newlines. Keep capital letters and punctuation as they are.
• Count overlapping n-grams. With n = 2, "a b a b" holds "a b" twice and "b a" once.
• Sort the (ngram, count) pairs by count, highest first. Break ties by the n-gram text in Python's string order, smallest first.
• Return at most k pairs. If there are fewer than k distinct n-grams, return all of them.
• Return a list of tuples, not a list of lists. The grader checks the types as well as the values.
• Annotate the counter as Counter[str]. Your code must pass mypy --strict.

Edge cases

• Return [] when n or k is less than 1.
• Return [] when the text has fewer than n words. Empty text has none.

Why most_common is not enough

Counter.most_common(k) breaks ties by first appearance, not alphabetically. Sorting its output afterwards does not help, because it may already have left out the n-gram that should win. For solve("zebra apple", 1, 1) the answer is [("apple", 1)], but most_common(1) gives [("zebra", 1)]. Sort all the counts with the key (-count, ngram), then take the first k.