-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
sortCharByFrequency.cpp
56 lines (50 loc) · 1.69 KB
/
sortCharByFrequency.cpp
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
* Given a string, sort it in decreasing order based on the frequency of characters.
* Example:
* Input: cccbbbbaa
* Output: bbbcccaa
*
* Input: AaaBBaa
* Output: aaaaBBA
*
* Input: cccaaa
* Output:cccaaa or aaaccc
*
* Notice that order of chars in alphabatical order does not matter for same frequency elements.
* However, also all the same characters should be together. cacaca will not be a valid answer.
*/
#include <iostream>
#include <unordered_map>
#include <map>
std::string frequencySort(std::string s) {
// Create a hash map of our characters with frequency as their values.
std::unordered_map<char,int> frequencyMap;
for (char c : s) {
frequencyMap[c]++;
}
// Now we will maintain an another ordered map whose key would be
// the frequency and values would be accumulated chars of same frequency.
//
std::map<int, std::string> stringMap;
for (auto frqPair : frequencyMap) {
char c = frqPair.first;
int n = frqPair.second;
stringMap[n] += std::string(n, c);
}
// Now pick the accumulated string in reverse order (highest first)
std::string result;
for (auto it = stringMap.rbegin(); it != stringMap.rend(); ++it) {
result += it->second;
}
return result;
}
int main()
{
std::string input1{"cccbbbbaa"};
std::cout << "Input: " << input1 << std::endl;
std::cout << "Output:" << frequencySort(input1) << std::endl;
std::string input2{"cccaaa"};
std::cout << "Input:" << input2 << std::endl;
std::cout << "Output:" << frequencySort(input2) << std::endl;
return 0;
}