Return the k most frequent words, ordered by frequency descending and lexicographic ascending on ties. Try it free and read the solution.

Top K Frequent Words

Path Sum III

Merge Sorted Array

Return the k most frequent words, ordered by frequency descending and lexicographic ascending on ties.

Given an array of strings `words` and an integer `k`, return the `k` most frequent words.

The output order is part of the problem definition: you **MUST** rank words by **frequency descending**, and when two words have the same frequency, you **MUST** break ties by **lexicographic (dictionary) ascending order**. Use exact **case-sensitive** string comparison for that tie-break, so every correct solution returns the same deterministic array whether it uses sorting, a heap, or another approach.

**Input / output**
- Input: `words: string[]`, `k: int`
- Output: `string[]`

**Examples**
1. `words = ["i","love","leetcode","i","love","coding"]`, `k = 2` returns `["i","love"]`.
2. `words = ["the","day","is","sunny","the","the","the","sunny","is","is"]`, `k = 4` returns `["the","is","sunny","day"]`.
3. `words = ["Apple","apple","Banana","banana","Apple","banana","Cherry","apple","banana","Cherry","Cherry"]`, `k = 3` returns `["Cherry","banana","Apple"]`.

**Constraints**
- `1 <= words.length <= 100000`
- `1 <= words[i].length <= 100`
- `1 <= k <=` the number of distinct words in `words`
- Words may repeat.
- Comparisons are case-sensitive.

**Follow-up**
If there are `m` distinct words, can you improve a full `O(m log m)` ranking into `O(m log k)` after counting frequencies by keeping only the current best `k` candidates in a heap?

- The raw array may contain many repeated words, but only distinct words matter once you know how often each one appears.
- Build a hash map from word to frequency.
- After that, every solution is just a different way to rank those distinct words by the required key: `(-frequency, word)`.

Count first, because ranking is based only on frequencies

- Count each word in a hash map.
- Put the distinct words into an array.
- Sort that array by frequency descending, then by lexicographic ascending order.
- Return the first `k` words.
- This is simple and deterministic, but it sorts all `m` distinct words, so it costs `O(m log m)` after counting.

Straightforward approach: count everything, then sort all distinct words

- Count frequencies exactly as before.
- Maintain a min-heap of size at most `k` whose root is the current **worst** candidate among the kept top `k` words.
- "Worse" means lower frequency, or on a frequency tie, lexicographically larger.
- Whenever the heap grows past `k`, remove that worst candidate.
- At the end, sort the remaining heap entries back into the required final order: frequency descending, lexicographic ascending.
- This reduces the ranking phase to `O(m log k)` when there are `m` distinct words.

Optimized final approach: keep only the best k words in a heap

- Many wrong answers count frequencies correctly but forget that ties must be resolved by lexicographic ascending order.
- That tie-break is required even in the heap version, so your heap comparator and your final output order must agree.
- Because comparison is case-sensitive, `"Apple" < "apple"` and `"Cherry" < "banana"` under ordinary string ordering.

Watch the tie-break carefully

Counting takes `O(n)` over the original array, and the heap-based ranking takes `O(m log k)` over the `m` distinct words. The auxiliary space is `O(m + k)` for the frequency map and heap.