hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Sort Characters By Frequency
Problem: 451. Sort Characters By Frequency
Problem Link: https://leetcode.com/problems/sort-characters-by-frequency/
Approach:
Counted the appearance of the characters.
Insert them into a priority_queue along with their appearance count and characters themselves.
Took the top of the priority_queue, concatenated the characters with the resultant string, and popped them out.
Returned the resultant string.
Time and Space Complexity:
Time complexity: O(n)
Space complexity: O(ClogC), where C = number of chars.
Code [C++]
class Solution {
public:
string frequencySort(string s) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = s.size();
vector<int>freq(80, 0);
for(int i=0; i<n; i++){
freq[s[i]-'0']++;
}
priority_queue<pair<int, char>>top_char;
for(char i='0'; i<='z'; i++){
if(freq[i-'0'] == 0) continue;
top_char.push(make_pair(freq[i-'0'], i));
}
s = "";
while(!top_char.empty()){
auto current = top_char.top();
top_char.pop();
for(int i=0; i<current.first; i++){
s += current.second;
}
}
return s;
}
};