#180MediumHeaps· Frequency Ranking with Tie-Breaks

Top K Frequent Words

A search engine logs the words typed into its search box and wants a "trending now" list of the `k` most frequent words. Given the list `words` and the integer `k`, return the `k` words with the highest number of occurrences, ordered from most frequent to least frequent. When two words occur equally often, the one that comes first alphabetically (dictionary order) ranks higher.

Input format

`words`: an array of lowercase strings; `k`: a positive integer.

Output format

An array of `k` distinct words, most frequent first, ties broken alphabetically.

Examples

Input: words = ["sun", "moon", "sun", "star", "moon", "sun"], k = 2

Output: ["sun", "moon"]

"sun" occurs 3 times and "moon" 2 times; "star" only once.

Input: words = ["b", "a", "c", "a", "b", "c", "d"], k = 3

Output: ["a", "b", "c"]

a, b and c all occur twice, so they are ranked alphabetically; "d" occurs once and is cut.

Input: words = ["x"], k = 1

Output: ["x"]

A single word is trending by default.

Constraints

1 <= words.length <= 10^4
1 <= words[i].length <= 10
words[i] consists of lowercase English letters
1 <= k <= number of distinct words

Study first

#heap
#hash-table
#sorting
#strings