The idea is to first create a counter map of frequency of each character in the string. Then create a list freq with an empty string corresponding to each possible frequency from 0 to max frequency observed in the counter. Go through the counter again and append each character f times(where f refers to its frequency in the string) to the string at the index corresponding to its frequency in freq. Now, go through the freq list in the reverse order and concatenate the strings to get the final result :)
from collections import Counter class Solution(object): def frequencySort(self, s): """ :type s: str :rtype: str """ if not s: return s c = Counter(s) res = '' freq = ['' for i in xrange(max(c.values())+1)] for ch in c: freq[c[ch]] += c[ch]*ch for j in xrange(len(freq)-1, -1, -1): res += freq[j] return res
Technically this is not O(n), the worst case scenario with no repeated chars makes this O(3n), and arguably O(4n) if we include the allocation of freq.
@Sparx Hi. O(4n) and O(3n) are both O(n). This is regular big O notation. you might find this helpful https://en.wikipedia.org/wiki/Big_O_notation
Slight optimization not sure if there is a better way to do it in python in logarithmic time.
from collections import Counter class Solution(object): def frequencySort(self, s): """ :type s: str :rtype: str """ #keeps a count of c = Counter(s) return_string = "" for item in c.most_common(len(s)): return_string = return_string + item*item return return_string ```
from collections import Counter
it's simple and easy to understand. But I think it will not meet the requirement of this question, because of the function Counter( )
@sharing-account It is an O(n) operation and so satisfies the requirements of the question at hand. I have also used Counter in interviews and it is acceptable.
@Devanshi OK, thx for your reply
@pg2286 Not the best solution considering string concatenation will take up a lot more space. It's always better to use a list to append and then combine using " ".join
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.