451.Sort Characters By Frequency

Tags: [map], [sort]

Link: https://leetcode.com/problems/sort-characters-by-frequency/?tab=Description

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

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.

Solution: map, sort

class Solution(object):
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return s

        frequency_map = {}
        for c in s:
            if c in frequency_map:
                frequency_map[c] += 1
            else:
                frequency_map[c] = 1

        char_frequency_arr = [(key, frequency_map[key]) for key in frequency_map]
        sorted_char_frequency_arr = sorted(char_frequency_arr, cmp=self.compare_char_by_frequency)
        new_s_char_arr = []
        for c, frequency in sorted_char_frequency_arr:
            for _ in xrange(frequency):
                new_s_char_arr.append(c)

        return ''.join(new_s_char_arr)

    @staticmethod
    def compare_char_by_frequency(item1, item2):
        return -(item1[1] - item2[1])

Note:

• Time complexity = O(nlgn), n is the number of characters of the given string, assume we are using the quick sort or merge sort to do the sorting.
• In Python, the only way to iterate the dictionary (map), is through the key: for key in dictionary.