Top K Frequent Characters

mediumSave

Hash TableHeapSortingString

Given a string s and an integer k, return the k most frequent characters. You may return the answer in any order. The input string s will only contain lowercase English letters.

Example 1

Input

[
  "aabbc",
  "2"
]

Output

["a","b"]

Explanation. Character 'a' appears 2 times, 'b' appears 2 times, 'c' appears 1 time. The 2 most frequent characters are 'a' and 'b'. Since 'a' and 'b' have the same frequency, their relative order in the output can be arbitrary.

Example 2

Input

[
  "aaabbcce",
  "3"
]

Output

["a","c","b"]

Explanation. Character 'a' appears 3 times, 'c' appears 2 times, 'b' appears 2 times, 'e' appears 1 time. The 3 most frequent characters are 'a', 'c', and 'b'. 'c' and 'b' have the same frequency, so their relative order doesn't matter.

Example 3

Input

[
  "abcdefghijklmnopqrstuvwxyza",
  "1"
]

Output

["a"]

Explanation. All characters from 'b' to 'z' appear once, while 'a' appears twice. Thus, 'a' is the most frequent character.

Example 4

Input

[
  "bbbbbaaaaa",
  "2"
]

Output

["b","a"]

Explanation. Character 'b' appears 5 times, 'a' appears 5 times. Both are equally frequent. The top 2 are 'b' and 'a' (order doesn't matter).

Example 5

Input

[
  "a",
  "1"
]

Output

["a"]

Explanation. The string has one character 'a', which appears 1 time. The top 1 frequent character is 'a'.

Example 6

Input

[
  "zyxw",
  "4"
]

Output

["z","y","x","w"]

Explanation. All characters appear once. Since k=4, all characters are returned. The order of characters with the same frequency does not matter.

Follow-up: Can you solve it in O(N log N) time complexity? What about O(N) time complexity, perhaps using a counting sort or bucket sort approach for frequencies?

Constraints:

- `1 <= s.length <= 10^5` - `s` consists of lowercase English letters. - `1 <= k <= 26` - It is guaranteed that `k` is less than or equal to the number of unique characters in `s`.

Views: 4