O(n) short Python solution with detailed explanation.


  • 1
    D

    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
    
    

  • -1
    S

    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.


  • 1
    D

    @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


  • 1
    P

    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
          ```

  • 0

    @pg2286 said in O(n) short Python solution with detailed explanation.:

    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( )


  • 0
    D

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


  • 0

    @Devanshi OK, thx for your reply


  • 0
    L

    @pg2286 Not the best solution considering string concatenation will take up a lot more space. It's always better to use a list to append and then combine using " ".join


  • 0
    P

    @haxet point noted would make sure to use list from now on for string concatenation


Log in to reply
 

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