Top K Frequent Characters
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.
[ "aabbc", "2" ]
[ "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.
[ "aaabbcce", "3" ]
[ "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.
[ "abcdefghijklmnopqrstuvwxyza", "1" ]
[ "a" ]
Explanation. All characters from 'b' to 'z' appear once, while 'a' appears twice. Thus, 'a' is the most frequent character.
[ "bbbbbaaaaa", "2" ]
[ "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).
[ "a", "1" ]
[ "a" ]
Explanation. The string has one character 'a', which appears 1 time. The top 1 frequent character is 'a'.
[ "zyxw", "4" ]
[ "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?
- `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
- 19