451. Sort Characters By Frequency
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
My Accepted Solution
n = i_str.size()
Time complexity: O(n)
Space complexity: O(1)
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;
}
};