451. Sort Characters By Frequency (Python)

Related Topic

Heap.

Description

Given a string, sort it in decreasing order based on the frequency of characters.

Sample I/O

Example 1

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Note

• S will consist of lowercase letters and have length in range [1, 500].

Methodology

Two ways to solve this question. Sort + HashMap and Heap

Sort + HashMap: Use hashmap to count frequence of each letter then sort the letter in descending order based on frequence.

Heap: Get frequence of each letter and push frequence and letter pair into heap. After pushed all frequence and letter pair into heap, then we pop and append the current letter*frequence to result string.

Sort + HashMap:

def frequencySort(self, s: str) -> str:
        dict = collections.Counter(s)
        ans = ''
        for c in sorted(dict, key=lambda item: dict[item], reverse=True):
            ans+=c*dict[c]
        return ans

BigO

Time complexity : O(nlogn) as sort will take O(nlogn)

Heap:

def frequencySort(self, s: str) -> str:
        heap = []
        for v, c in collections.Counter(s).items():
            heapq.heappush(heap,[-c,v])
        res = ""
        while heap:
            c, v = heapq.heappop(heap)
            res += v*-c
        return res

BigO

Time complexity : O(nlogn) as we construct heap will take O(nlogn)