Top K Frequent Words

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

Return the answer sorted by frequency from highest to lowest. If two words have the same frequency, sort them in alphabetical order.

Examples

Input: words = ["i","love","leetcode","i","love","coding"], k = 2

Output: ["i","love"]

Explanation: "i" and "love" are the two most frequent words. "i" appears 2 times and "love" appears 2 times. "i" comes before "love" alphabetically.

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4

Output: ["the","is","sunny","day"]

Explanation: "the" appears 4 times, "is" 3 times, "sunny" 2 times, and "day" 1 time. They are sorted by frequency, with ties broken alphabetically.

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

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

Explanation: All words appear once, so they are sorted alphabetically.

Constraints

• 1 <= words.length <= 500
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, number of unique words].
• The answer is guaranteed to be unique.