Xóa trùng lặp kề nhau trong chuỗi II trong C++

Cho chuỗi s và số nguyên k. Lặp lại việc xóa k ký tự giống nhau liên tiếp cho đến khi không thể xóa thêm. Trả về chuỗi cuối cùng.

Ví dụ: s = "deeedbbcccbdaa", k = 3 → xóa "eee", "ccc" → "ddbbbaa" → xóa "bbb" → "dddaa" → xóa "ddd" → "aa".

Thuật toán giải quyết (Stack cặp ký tự-số lượng)

1. Stack lưu cặp (char, count).
2. Duyệt chuỗi:
   • Nếu stack rỗng hoặc ký tự khác đỉnh stack → push (c, 1).
   • Ngược lại → tăng count đỉnh stack.
   • Nếu count đạt k → pop.
3. Xây dựng kết quả từ stack (đảo ngược vì stack LIFO).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> st;
        for (char c : s) {
            if (!st.empty() && st.back().first == c) {
                st.back().second++;
                if (st.back().second == k) st.pop_back();
            } else {
                st.push_back({c, 1});
            }
        }
        string ans;
        for (auto &p : st) ans.append(p.second, p.first);
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.removeDuplicates("deeedbbcccbdaa", 3);
}

Đầu vào

"deeedbbcccbdaa" 3

Đầu ra

aa