Return the Ten Most Frequent Words

Return the ten most frequent words in a collection, or all distinct words if fewer than ten appear.

Function Contract

Implement top_ten_words(words) -> list[str], where words is an array of already tokenized lowercase words.

Rank words by descending occurrence count. Break ties by ascending lexicographic order. Return only the words in this order, with no duplicates.

Constraints and Clarifications

Tokenization and tie-breaking are explicit practice assumptions that make the result deterministic.

• 0 <= len(words) <= 200000.
• Each word contains only lowercase English letters and has length from 1 through 100.
• The total number of characters in the input is at most 2000000.
• Every occurrence counts; there is no stop-word filtering.
• Return [] for an empty input.
• The result contains min(10, number of distinct words) entries.

Examples

words = ["pear", "apple", "pear", "banana", "apple", "pear"]
Output: ["pear", "apple", "banana"]

words = ["kiwi", "apple", "banana", "kiwi", "banana", "apple"]
Output: ["apple", "banana", "kiwi"]

All words in the second example have the same frequency, so the tie rule determines their order.

Hint: Separate counting from selecting ten entries

The number of distinct words can be much larger than the output size. Consider how much ordering is needed after each word's total count is known.

Ten Most Frequent Words

You are given words, a list of already tokenized lowercase words. Return the ten most frequent words, or all distinct words if fewer than ten distinct words appear.

Implement top_ten_words(words), which returns a list of strings.

Rank words by descending occurrence count. Break ties by ascending lexicographic order. Return only the words in this order, with no duplicates. Every occurrence counts; there is no stop-word filtering. The result contains exactly min(10, number of distinct words) entries, and an empty input returns [].

Example 1

Input: words = ["pear", "apple", "pear", "banana", "apple", "pear"]
Output: ["pear", "apple", "banana"]

pear appears 3 times, apple 2 times and banana once.

Example 2

Input: words = ["kiwi", "apple", "banana", "kiwi", "banana", "apple"]
Output: ["apple", "banana", "kiwi"]

All words have the same frequency, so ascending lexicographic order determines their order.

Constraints

• 0 <= len(words) <= 200000
• Each word contains only lowercase English letters a-z and has length from 1 through 100.
• The total number of characters in the input is at most 2000000.
• No count can exceed 200000, so every count fits in a 32-bit signed integer.

Hints

1. The number of distinct words can be much larger than the output size. First work out each word's total count.
2. Once every count is known, think about how much ordering you actually need to pick out ten entries.
3. Ties are ordered by the words themselves, and a word that is a prefix of another comes first.

Approach

Count every word's occurrences with a hash map in one pass. Then sort the distinct (word, count) entries by the key (descending count, ascending word) and keep the first ten words. Invariant: after the counting pass each distinct word appears exactly once in the map, with its total occurrence count, so the result can never contain duplicates. The sort key is exactly the ranking the problem defines. Counts are compared first, so a more frequent word always beats a lexicographically smaller one. Among equal counts, plain string comparison puts a prefix before its extensions ('a' before 'ab'). This is also correct when ties straddle the 10th/11th position, because the full order is fixed before truncation. Taking a prefix of length min(10, distinct) gives the required size. Edge cases: an empty input gives an empty map and returns []; fewer than ten distinct words returns all of them; since words are lowercase ASCII only, code-point comparison equals lexicographic order in every language. Keeping a bounded heap of size 10 instead of sorting would reduce the selection step to O(d log 10).

• Time complexity: O(L + d log d · m), where L is the total number of characters, d is the number of distinct words and m <= 100 is the maximum word length
• Space complexity: O(L)