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.

&nbsp;
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"


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	2 &lt;= k &lt;= 104
	s only contains lowercase English letters.


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack=[]
        res=''
        for i in range(len(s)):
            if len(stack)==0:
                stack.append([s[i],1])
            elif stack[-1][0]==s[i]:
                stack[-1][1]=stack[-1][1]+1
            else:
                stack.append([s[i],1])
            if stack[-1][1]==k:
                stack.pop()
        for i in range(len(stack)):
            res+=stack[i][0]*stack[i][1]
        return res
class Solution
{
    public String removeDuplicates(String s, int k)
    {
        int i = 0 ;
        StringBuilder newString = new StringBuilder(s) ;
        int[] count = new int[newString.length()] ;
        while( i < newString.length() )
        {
            if( i == 0 || newString.charAt(i) != newString.charAt( i - 1 ) )
            {
                count[i] = 1 ;
            }
            else
            {
                count[i] = count[ i - 1 ] + 1 ;
                if( count[i] == k )
                {
                    newString.delete( i - k + 1 , i + 1 ) ;
                    i = i - k ;
                }
            }
            i++ ;
        }
        return newString.toString() ;
    }
}
#define pp pair< int , char > 

class Solution {
public:
    string removeDuplicates(string s, int k) {
        
        int n=s.size();
        
        stack< pp > stk;
        
        int i=0;
        
        while(i<n)
        {
            int count=1;
            
            char ch=s[i];
            
            while((i+1)<n && s[i]==s[i+1])
            {
                i++;
                count++;
            }
         
            int c=0;
            
            if(!stk.empty() && stk.top().second==ch)
            {
                c+=stk.top().first;
                stk.pop();
            }
            
            count+=c;
            
            count=count%k;
            
            if(count!=0)
            {
                stk.push({count , ch});
            }
            
            i++;
            
            
        }
        
        string str="";
        
        while(!stk.empty())
        {
            int count=stk.top().first;
            
            while(count--)
            {
                str.push_back(stk.top().second);
            }
            
            stk.pop();
        }
        
        reverse(str.begin() , str.end());
        
        return str;
        
    }
};
var removeDuplicates = function(s, k) {
  const stack = []
  for(const c of s){
    const obj = {count: 1, char: c}
    if(!stack.length){
      stack.push(obj)
      continue
    }
    const top = stack[stack.length-1]
    if(top.char === obj.char && obj.count + top.count === k){
      let count = k
      while(count > 1){
        stack.pop()
        count--
      }
    }else if(top.char === obj.char){
      obj.count+=top.count
      stack.push(obj)
    }else{
      stack.push(obj)
    }
  }
  return stack.reduce((a,b)=> a+b.char, '')
};
Remove All Adjacent Duplicates in String II