451. Sort Characters By Frequency

2020, Nov 27 2 mins read

1. Description

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

2. Example

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.

3. Solutions

Sorting

n = i_str.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution
{
public:
    // string frequencySort(string s)
    string frequencySort(string &i_str)
    {
        vector<pair<char, int>> charAndTimes(256);
        for(int i = 0; i < i_str.size(); i++)
        {
            charAndTimes[i_str[i]].first = i_str[i];
            charAndTimes[i_str[i]].second++;
        }

        sort(charAndTimes.begin(), charAndTimes.end(), [](pair<char, int> left, pair<char, int> right){return left.second > right.second;});

        string result;
        for(int i = 0; i < charAndTimes.size() && charAndTimes[i].second > 0; i++)
        {
            auto item = charAndTimes[i];
            result += string(item.second, item.first);
        }

        return result;
    }
};

Search

Tags