1209. Remove All Adjacent Duplicates in String II

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

c++

class Solution {
    int isDuplicate(list<char> &l, int k) {
        if (l.size() < k) return l.size();
        auto it = l.begin();
        int i = k;
        while (i--) {
            if (*it != l.front()) return k - i - 1;
            it++;
        }
        return -1;
    }

    void __pop_front(list<char> &l, int k) {
        while (k--) l.pop_front();
    }

    void __push_front(list<char> &from, list<char> &to, int k) {
        while (k-- && from.size()) {
            to.push_front(from.back());
            from.pop_back();
        }
    }

    void __push_back(list<char>& from, list<char>& to, int k) {
        while(k-- && from.size()) {
            to.push_back(from.front());
            from.pop_front();
        }
    }

public:
    string removeDuplicates(string s, int k) {
        list<char> res, ss(begin(s), end(s));
        while (ss.size()) {
            int dup = isDuplicate(ss, k);
            if (dup == -1) {
                __pop_front(ss, k);
                __push_front(res, ss, k);
            } else {
                __push_back(ss, res, dup);
            }
        }
        return string(res.begin(), res.end());
    }
};