Maximal String

• Time : $O(|A|log|A|)$
• Space : $O(B)$

string Solution::solve(string A, int B) {
    string s = A;
    sort(rbegin(s), rend(s));
    string res = "";
    unordered_map<char, vector<char>> mp;
    unordered_map<char, int> freq;
    for(int i = 0; i < A.size(); i++) {
        if(s[i] == A[i]) res.push_back(s[i]);
        else if(s[i] > A[i] and B) {
            B -= 1;
            res.push_back(s[i]);
            mp[s[i]].push_back(A[i]);
            freq[s[i]]++;
        } else {
            vector<char>& now = mp[A[i]];
            sort(begin(now), end(now));
            while(freq[now.back()]) {
                freq[now.back()]--;
                char b = now.back(); now.pop_back();
                if(b != A[i]) {
                    sort(begin(mp[b]), end(mp[b]));
                    now.push_back(mp[b].back());
                    mp[b].pop_back();
                    sort(begin(now), end(now));
                }
            }
            res.push_back(now.back());
            now.pop_back();
        }
    }
    return res;
}