# O(n) short Python solution with detailed explanation.

• 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[0]*item[1]
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.