Reverse Shuffle Merge

• Time : O(n)
• Space : O(n)

string reverseShuffleMerge(string s) {
    unordered_map<char, int> freq;
    unordered_map<char, int> req;
    reverse(begin(s), end(s));
    for(auto& ch : s) freq[ch]++;
    for(auto& [k, v] : freq) req[k] = v / 2;
    string res = "";
    
    for(int i = 0; i < s.length(); i++) {
        if(req[s[i]]) {
            while(!res.empty() and res.back() > s[i] and freq[res.back()] >= req[res.back()] + 1) {
                req[res.back()]++;
                res.pop_back();
            }
            res.push_back(s[i]);
            req[s[i]]--;
        }
        freq[s[i]]--;
    }
    return res;
}