Given a string s, 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 <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

Difficulty: interview

Starter code:

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        

Solutions:
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        st=[['*',0]]
        for c in s:
            if c!=st[-1][0]:
                st.append([c,1])
            else:
                st[-1][1]+=1
                if st[-1][1]==k:
                    st.pop()
        res=''
        for c,v in st:
            res+=c*v
        return res

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if not s or k == 0:
            return s
        
        stack = [['#', 0]]
        for c in s:
            if stack[-1][0] == c:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([c, 1])
        

        return ''.join(c*k for c, k in stack)

        
        


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        res = []
        char = s[0]
        count = 1

        for i in range(1, len(s)):
            if s[i] == char:
                count += 1
            else:
                count = 1
                char = s[i]

            if count == k:
                return self.removeDuplicates(s[:i-k+1] + s[i+1:], k)
            
        return s

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if len(s) < k:
            return s
        # stack=[]
        # cnt_stack=[]
        # for char in s:
        #     if not stack or stack[-1] !=char:
        #         stack.append(char)
        #         cnt_stack.append(1)
        #     else:
        #         cnt_stack[-1] +=1
        #     if cnt_stack[-1] == k:
        #         cnt_stack.pop()
        #         stack.pop()
        # return ''.join([stack[i]*cnt_stack[i] for i in range(len(stack))])
        stack=[[0,'#']]
        for char in s:
            if char == stack[-1][1]:
                stack[-1][0] +=1
                if stack[-1][0] == k:
                    stack.pop()
            else:
                stack.append([1,char])
        return ''.join(c*k for c,k in stack)
            
                    
                
        
               


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str: 
        
        unique = set(s)
        dups = []
        
        for c in unique: 
            dups.append(c*k)
            
        while True: 
            start = s
            for c in dups: 
                s = s.replace(c, '')
                
            if start == s: 
                return s
        
#         ret = list(s) 
        
#         while True: 
#             s = ret
#             ret = []
#             ac = 1
#             for c in s: 
#                 if not ret or ret[-1] != c: 
#                     ac = 1
#                     ret.append(c)
#                 else: 
#                     if ac + 1 == k: 
#                         while ac: 
#                             ret.pop()
#                             ac -= 1
#                     else: 
#                         ret.append(c)
#                         ac += 1
#                 # print(ret, ac)
#             if len(ret) == len(s): 
#                 break
                        
#         return ''.join(ret)
                    


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        lengths = [[None, 0]]
        idx = 0
        
        while idx < len(s):
            current = lengths[-1][0]
            
            if current == s[idx]:
                lengths[-1][1] += 1
            else:
                lengths.append([s[idx], 1])
                current = s[idx]
                
            if lengths[-1][1] == k:
                lengths.pop()
                s = s[:idx - k + 1] + s[idx + 1:]
                idx -= k
                
            idx += 1
                    
        return s

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        
        ret = list(s) 
        
        while True: 
            s = ret
            ret = []
            ac = 1
            for c in s: 
                if not ret or ret[-1] != c: 
                    ac = 1
                    ret.append(c)
                else: 
                    if ac + 1 == k: 
                        while ac: 
                            ret.pop()
                            ac -= 1
                    else: 
                        ret.append(c)
                        ac += 1
                # print(ret, ac)
            if len(ret) == len(s): 
                break
                        
        return ''.join(ret)
                    


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        
        
        count = 1
        flag = 1
        last_idx = 0
        while(1):
            i = 0
            temp_s = s
            while(i < len(s)-1):
                #print(\"i = \",i)
                #print(\"s = \",s)
                if(s[i] != s[i+1]):
                    i = i+1
                else:
                    last_idx = i
                    while(1):
                        if(i+1 == len(s)):
                            break 
                        elif(s[i] == s[i+1]):
                            count = count+1
                            i = i+1
                        else:
                            break 
                    if(count >= k):
                        s = s[:last_idx] + s[last_idx+k:]
                        i = last_idx
                    count = 1
            if(temp_s == s):
                break 
        return s

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        while True:
            stk = []
            s_new = []
            for c in s:
                if len(stk)==k: stk=[]
                while stk and c!=stk[-1]:
                    s_new.append(stk.pop())
                stk.append(c)
                if len(stk)==k: stk=[]
            while stk:
                s_new.append(stk.pop())  
            print(''.join(s_new))
            if s==s_new: break
            s = s_new
        return ''.join(s)

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        
        ns = []
        deleted= True
        while deleted:
            deleted = False
            i = 0
            ns = []
            while i < len(s):
                if i <= len(s) - k and s[i+1:i+k] == s[i]*(k-1):
                    deleted = True
                    i += k
                else:
                    ns.append(s[i])
                    i += 1
            s = ''.join(ns)

        return s

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        
        def helper(s):
        
            ans = []
        
            i = 0
            while i < len(s):
            
                if s[i] * k != s[i:i+k]:
                    ans.append(s[i])
                    i += 1
                else:
                    i += k
        
            if len(ans) == len(s):
                res.append(''.join(ans))
                return
            else:
                helper(''.join(ans))

        res = []
        helper(s)
        return res[0]

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        sliced = True
        while sliced == True:
            s, sliced = self.getSlices(s, k)
        return s
    
    def getSlices(self, s, k):
        sliced = False
        idx = set()
        i = 0
        while i < len(s):
            if s[i]*k == s[i:i+k]:
                idx.update(range(i, i+k))
                sliced = True
                i += k
            i += 1
        if sliced:
            new_str = ''.join([char for i, char in enumerate(s) if i not in idx])
            return new_str, sliced
        return s, sliced

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        while True:
            stk = []
            s_new = []
            for c in s:
                if len(stk)==k: stk=[]
                while stk and c!=stk[-1]:
                    s_new.append(stk.pop())
                stk.append(c)
                if len(stk)==k: stk=[]
            while stk:
                s_new.append(stk.pop())  
            if s==s_new: break
            s = s_new
        return ''.join(s)

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        len_s = len(s)
        
        if k > len_s:
            return s
        
        def helper(string, itr_range):
            not_found = False    #if no k repeating elements found, then True
            
            while not not_found:
                not_found = True
                
                for i in range(itr_range):
                    if string[i:i+k] == string[i]*k:
                        string = string[:i]+string[i+k:]
                        itr_range = len(string)-k+1
                        not_found = False
                        break
            return string
        
        return helper(s, len_s-k+1)

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if len(s)<k:
            return s
        found = self.findStr(s, k)
        if not found:
            return s
        else:
            return self.removeDuplicates(s.replace(found, ''), k)
        
    def findStr(self, s:str, k:int):
        for i in range(len(s)):
            if (s[i]*k) in s:
                return s[i]*k
        return None

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        distinct = len(set(s))
        while len(s) >= k:
            new_s = ''
            cur, count = s[0], 1
            for i in range(1, len(s)):
                print(cur, count)
                if s[i] == cur:
                    count += 1
                else:
                    new_s += cur * (count % k)
                    cur, count = s[i], 1
            new_s += cur * (count % k)
            if s == new_s:
                break
            s = new_s
        return s


class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        duplicates=[k*i for i in 'abcdefghijklmnopqrstuvwxyz']
        counter=0
        while counter!=len(s):
            counter=len(s)
            for i in duplicates:
                s=s.replace(i,'')
                
        return s

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
                
        if not s:
            return ''
        
        stack = []
        
        prev = count = None
        for i in range(0, len(s)):
            
            if not prev:
                prev, count = s[i], 1
            elif s[i] == prev:
                count += 1
            else:
                stack.append((prev, count))
                prev = s[i]
                count = 1
                
            if count == k:
                if stack:
                    prev, count = stack.pop()
                else:
                    prev = None
            
            # print(stack, s[i], i, prev, count)
            
        stack.append((prev, count))
        
        output = ''
        for e,c in stack:
            output += e*c
        
        return output
        
        
        
            
                
            
            
                
'''
#check k = 1
'''

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = [['#', 0]]
        for c in s:
            if stack[-1][0] == c:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([c, 1])
        return ''.join(c * k for c, k in stack)