Python solution using a dictionary O(n)

  • 0
    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])

  • 2

    This is an O(n log n) since you have the sorting step.

  • 1

    @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).

  • 0


    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

  • 0

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

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.