Remove All Adjacent Duplicates in String II ใน C++: ลบตัวอักษรติดกัน k ตัว

โจทย์

กำหนดสตริง s และจำนวน k ลบกลุ่มตัวอักษรเดียวกันที่ติดกัน k ตัวซ้ำๆ จนไม่สามารถลบได้แล้ว คืนสตริงสุดท้าย

ตัวอย่าง: s="deeedbbcccbdaa", k=3 → ลบ "eee","ccc" → "ddbbbdaa" → ลบ "bbb" → "dddaa" → ลบ "ddd" → "aa"

แนวคิด: Stack เก็บ (ตัวอักษร, จำนวนติดต่อกัน)

อ่านซ้ายไปขวา เก็บคู่ (char, count) ใน stack ถ้า count == k → pop ออก

ขั้นตอน

1. สร้าง stack<pair<char,int>> st
2. ลูป i = 0 ถึง n (รวม n เพื่อ flush stack ท้ายสุด):
   • ถ้า !st.empty() && st.top().second == k → st.pop()
   • ถ้า i == n → break
   • ถ้า st.empty() || st.top().first != s[i] → st.push({s[i], 1})
   • มิฉะนั้น → st.top().second++
3. สร้างผลลัพธ์จาก stack (ต้อง reverse เพราะ stack เป็น LIFO)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    string removeDuplicates(string s, int k) {
        string ans;
        stack<pair<char, int>> st;
        int n = s.size();
        
        for (int i = 0; i <= n; ) {
            if (!st.empty() && st.top().second == k) st.pop();
            if (i == n) break;
            char c = s[i];
            if (st.empty() || st.top().first != c) {
                st.push({c, 1});
            } else {
                st.top().second++;
            }
            i++;
        }
        
        while (!st.empty()) {
            auto [c, cnt] = st.top(); st.pop();
            ans.append(cnt, c);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

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

อินพุต / เอาต์พุต

Input: "deeedbbcccbdaa" 3

Output: aa

ความซับซ้อน

• Time: O(n) - แต่ละตัวอักษร push/pop สูงสุด 1 ครั้ง
• Space: O(n) - stack