Voldemort_007's blog

By Voldemort_007, history, 3 years ago, In English

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)

  • Vote: I like it
  • -20
  • Vote: I do not like it

| Write comment?