Python solution with detailed explanation


  • 0
    G

    Solution

    Sort Characters By Frequency https://leetcode.com/problems/sort-characters-by-frequency/

    Frequency of a char is between 0 to len(s)

    • Frequency of a character can vary from 0 to len(s).
    • Create a hashmap H1 of character to character frequency for the input string.
    • Iterate H1 to create hashmap H2 with key as frequency and value as substrings of repeated strings with length as the frequency.
    • Finally lookup all potential frequencies in decreasing order in H2 and produce the final result.
    from collections import Counter, defaultdict
    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            c1 = Counter(s), defaultdict(int)
            for k,v in c1.items():
                c2[v].append(k*v)
            return "".join(["".join(c2[i]) for i in range(len(s), -1, -1) if i in c2])
    

    Using most_common() API

    • Notice the usage of most_common() in Counter API.
    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            return "".join([c*v for c,v in Counter(s).most_common()])
    

    Sorting the char, freq tuples

    from collections import Counter
    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            return "".join([k*v for k,v in sorted(Counter(s).items(), key=lambda x:x[1], reverse=True)])
    

Log in to reply
 

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