class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
map = {}
for c in s:
map[c] = map.get(c, 0) + 1
items = map.items()
items.sort(key=lambda tup: tup[1], reverse=True)
return ''.join([letter*count for letter, count in items])
Python solution using a dictionary O(n)

@intelaka It's not. The sorting step is O(A*logA) where A is the size of the alphabet. If we consider only lowercase characters, it would be 26. So you could even consider this step as a constant. The dominant loop is the loop that iterates through all the characters. Hence the overall complexity is O(N).

Limiting the input to a small range of ASCII characters doesn't magically make it constant and lower the complexity. ASCII characters are just binary strings in the set of natural numbers 1 to infinity. So as the range of the input set increases, it approaches O(n log n). The best you could probably get away with here is O(n + k) using a radix sort

@siddhartha6 Let us assume all characters are independent. This solution would be O(nlgn) in the worst case as A=n in this case.