Question Link —
https://practice.geeksforgeeks.org/problems/game-with-string4100/1#
Method 1 —
int minValue(string a, int k){
int freq[26] = {0}; //O(n) for(int i = 0;i < a.size();i++) freq[a[i] - 'a']++; //O(26) priority_queue<int>q(freq,freq+26); //O(k * log(26) while(k && a.size() > 0) { int p = q.top(); q.pop(); k--; q.push(p-1); } //O(26*log26) int ans = 0; while(q.size() > 0) { int p = q.top(); ans += p * p; q.pop(); } return ans; }
Time — O(k*log26) Space — O(26)
Method 2 —
int minValue(string a, int k){
unordered_map<char,int>mp; //O(n) for(int i = 0;i < a.size();i++) mp[a[i]]++; priority_queue<int>q; //O(n*logn) in worstCase for(auto i : mp) q.push(i.second); //O(k * log(n) while(k && a.size() > 0) { int p = q.top(); q.pop(); k--; q.push(p-1); } //O(n*logn) int ans = 0; while(q.size() > 0) { int p = q.top(); ans += p * p; q.pop(); } return ans; }
Time — O(nlogn) Space — O(n)