Python solution using a dictionary O(n)


  • 0
    J
    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
    I

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


  • 1
    S

    @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
    W

    @siddhartha6

    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
    A

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