Solution: Top K Frequent Words

Statement

Given a list of strings words and an integer k, return the k most frequently occurring strings.

Note: The result should be sorted in descending order based on frequency. If multiple words have the same frequency, they should be sorted in lexicographical order.

Constraints:

• $1 \leq$ words.length $\leq 100$

• $1 \leq$ words[i].length $\leq 10$

• $1 \leq$k $\leq$ number of unique words in the list

• words[i] consists of lowercase English letters.

Solution

This solution utilizes the trie data structure and bucket sort method to find the top k elements in a list. It achieves this by combining a bucket sort technique (which groups words based on their frequencies), a trie (which stores words in an organized manner), and a frequency map (which counts the occurrences of each word).

Let’s look at the step-by-step implementation of the solution:

• Initialize a frequency_map dictionary to count the frequency of each word in the words list.

• Create a list of buckets where the index represents the frequency of words. The length of this list is one more than the number of words to accommodate the maximum possible frequency.

• For each word and its frequency from the frequency_map:

  • Add the word to the corresponding bucket (indexed by its frequency).

  • Initialize each bucket with a trie that stores words with the same frequency.

• Next, iterate over buckets from the highest frequency to the lowest. For each nonempty trie:

  • Retrieve all words stored in it.

  • If the number of retrieved words is less than k, add all of them to top_k and decrement k by the number of added words.

  • Otherwise, add only the top k words (sorted lexicographically) to top_k and terminate the loop.

• Return the top_k containing the top k elements sorted according to their frequencies.

Let’s look at the following illustration to get a better understanding of the solution: