Simple Python Solution


  • 0
    J
    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            # Store in a dictionary
            charMapping = {}
            for character in s:
                if character in charMapping:
                    charMapping[character] = charMapping[character] + 1
                else:
                    charMapping[character] = 1
            # Now, create the array list
            lst = []
            for char, count in charMapping.iteritems():
                lst.append([count, char])
            # Sort it now
            lst.sort(key= lambda x: x[0], reverse= True)
            # Now, add to string
            newStr = ""
            for item in lst:
                newStr = newStr + (item[1] * item[0])
            # Return
            return newStr
    

    Got a runtime of 82ms and it passed all the test cases!


  • 0
    K
    for item in lst:
        newStr = newStr + (item[1] * item[0])
    

    If I change newStr = newStr + (item[1] * item[0]) to a for loop
    then it will complain that time limit exceeded.

    for item in lst:
        for i in range(item[0])
            newStr += item[1]
    

    Don't know why does it happen


  • 2
    K

    @kyao4 I think it allocates a character multiple times in memory with the way you suggest, or at least it performs a concatenation multiple times, while item[1] * item[0] is practically constructed in constant time and you have one concatenation.


Log in to reply
 

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