Problem Link
Problem:
Given a string S and an integer K, you need to output the characters with a frequency greater than or equal to K, sorted in lexicographical order.
Approach:
We can use an ordered map (TreeMap in Java) to store the frequencies of all the characters in sorted order. After populating the frequency map, iterate through it and select characters with frequencies greater than or equal to K.
Complexity:
-
Time Complexity:
O(N), Traversed the whole string once to store the frequencies. -
Space Complexity:
O(1), We store the frequency of each character in the map. Taking both lower and uppercase, the maximum space it can take isO(52)→O(26)for lowercase andO(26)for uppercase. AsO(52)is a constant, the space complexity will beO(1).