Most Frequent Words

Write top_words(text, k) that finds the k most common words in text and returns them as a list of (word, count) tuples, most common first. When two words have the same count, the one that comes first alphabetically goes first. If text has fewer than k different words, return all of them.

Words are case-insensitive, so return them in lowercase. A word is a run of letters a-z, and an apostrophe between two letters belongs to the word ("don't", "rock'n'roll"). Every other character separates words, including digits and an apostrophe at the start or end of a word.

Examples

top_words("The cat and the hat. The END, and the end!", 2)
# returns [('the', 4), ('and', 2)]
top_words("Don't stop. Don't STOP believing", 3)
# returns [("don't", 2), ('stop', 2), ('believing', 1)]
top_words("", 3)  # returns []

In the first example "and" and "end" both appear twice, and "and" wins the tie because it comes first alphabetically.

Constraints

• text has 0 to 100,000 ASCII characters.
• 1 <= k <= 1000