Given a string s, sort it in decreasing order based on the frequency of characters, and return the sorted string.
Example 1:
Input: s = "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: s = "cccaaa"
Output: "aaaccc"
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: s = "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: (Counting Frequency and sorting)
Approach:
Counting Frequency
Storing in a vector and sorting
class Solution
{
public:
static bool cmp(pair<int, char> &a, pair<int, char> &b)
{
return a.first > b.first;
}
string frequencySort(string s)
{
unordered_map<char, int> m;
for (int i = 0; i < s.length(); i++)
{
m[s[i]]++;
}
vector<pair<int, char>> v;
for (auto itr = m.begin(); itr != m.end(); itr++)
{
v.push_back({itr->second, itr->first});
}
sort(v.begin(), v.end(), cmp);
string res = "";
for (int i = 0; i < v.size(); i++)
{
res.append(v[i].first, v[i].second);
}
return res;
}
};
Time Complexity: O(n log n)
Solution: (Bucket Sort)
class Solution
{
public:
string frequencySort(string s)
{
int n = s.length();
unordered_map<char, int> m;
for (int i = 0; i < s.length(); i++)
{
m[s[i]]++;
}
vector<string> bucket(n + 1, "");
for (auto itr = m.begin(); itr != m.end(); itr++)
{
int count = itr->second;
char ch = itr->first;
bucket[count].append(count, ch);
}
string res = "";
for (int i = n; i >= 0; i--)
{
res += bucket[i];
}
return res;
}
};