Last active
May 22, 2020 12:31
-
-
Save Gowtham-369/42f99172ad4a12bc4cb719c3f391ac68 to your computer and use it in GitHub Desktop.
Day 21:LeetCode 30 Day May Challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Given a string, sort it in decreasing order based on the frequency of characters. | |
| 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. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| /* | |
| bool mycomp(pair<int,char> a,pair<int,char> b){ | |
| //non_increasing order | |
| return (a.first>b.first); | |
| } | |
| */ | |
| string frequencySort(string s) { | |
| vector<pair<int,char>> v; | |
| unordered_map<char,int> mp; | |
| //int n = s.size(); | |
| for(char x : s){ | |
| mp[x]++; | |
| } | |
| /* | |
| for(auto it=mp.begin(); it!=mp.end(); it++){ | |
| v.push_back({it->second,it->first}); | |
| } | |
| */ | |
| for(auto p:mp){ | |
| //v.push_back(make_pair(p.second,p.first)); | |
| v.push_back({p.second,p.first}); | |
| } | |
| //sort(v.begin(),v.end(),mycomp); | |
| sort(v.begin(),v.end(),[](pair<int,char> a,pair<int,char> b){return a.first>b.first;}); | |
| string ans = ""; | |
| for(auto p:v){ | |
| int n=p.first; | |
| while(n--){ | |
| ans+=p.second; | |
| } | |
| } | |
| return ans; | |
| } | |
| }; | |
| //METHOD -2 | |
| //consumes a lot of space,if frequency of character is large like 42167989737 | |
| class Solution { | |
| public: | |
| string frequencySort(string s) { | |
| unordered_map<char,int> freq; | |
| vector<string> bucket(s.size()+1, ""); | |
| string res; | |
| //count frequency of each character | |
| for(char c:s) freq[c]++; | |
| //put character into frequency bucket | |
| for(auto& p:freq) { | |
| int n = p.second; | |
| char c = p.first; | |
| bucket[n].append(n, c); | |
| //fill | |
| //Appends n consecutive copies of character c. | |
| } | |
| //form descending sorted string | |
| //need s.size()+1 because we travel upto 1 and also we dont insert empty("") characters in vector | |
| for(int i=s.size(); i>0; i--) { | |
| if(!bucket[i].empty()) | |
| res.append(bucket[i]); | |
| } | |
| return res; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment