1209. Remove All Adjacent Duplicates in String II

1209. Remove All Adjacent Duplicates in String II | LeetCode Solution

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.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 105
2 <= k <= 104
s only contains lower case English letters.

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<pair<char,int>>st;
        
        for(int i=0; i<s.length(); i++){
            
            if(st.empty()){
                st.push({s[i],1});
            }
            else {
                if(st.top().first==s[i]){
                    st.top().second++;
                    if(st.top().second==k){
                        st.pop();
                    }
                }
                else{
                    st.push({s[i],1});
                }
            }
            
        }
        string ans="";
        // cout<<st.size();
        while(!st.empty()){
            
           while(!st.empty() && st.top().second!=0){
               ans+=st.top().first;
               st.top().second--;
                    // cout<<st.top().second<<endl;
               if(st.top().second==0)
                   st.pop();
           } 
            
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};