Count the most frequent words

The problem

Return the k most frequent words in text as [word, count] pairs. Words are runs of letters or apostrophes, compared case-insensitively. Order by count descending, then word ascending.

Function: def top_words(text,k):

Example input (a JSON list of arguments): ["the cat and the hat and the bat", 2]
Expected output: [["the", 3], ["and", 2]]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Lower-case the text, extract words with a regular expression and count them with collections.Counter.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def top_words(text,k):
    import re
    from collections import Counter
    counts=Counter(re.findall(r"[a-z']+",text.lower()))
    return [[word,count] for word,count in sorted(counts.items(),key=lambda item:(-item[1],item[0]))[:k]]

Why it works

Lower-case the text, extract words with a regular expression and count them with collections.Counter. Counter.most_common breaks ties by first appearance, so sort by (-count, word) yourself when the problem asks for alphabetical ties.

Complexity: O(n + w log w) time / O(w) space for w distinct words.

Time: O(n + w log w) time · Space: O(w) space for w distinct words