<p>You are given a string <code>s</code> and an integer <code>k</code>, a <code>k</code> <strong>duplicate removal</strong> consists of choosing <code>k</code> adjacent and equal letters from <code>s</code> and removing them, causing the left and the right side of the deleted substring to concatenate together.</p>

<p>We repeatedly make <code>k</code> <strong>duplicate removals</strong> on <code>s</code> until we no longer can.</p>

<p>Return <em>the final string after all such duplicate removals have been made</em>. It is guaranteed that the answer is <strong>unique</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcd&quot;, k = 2
<strong>Output:</strong> &quot;abcd&quot;
<strong>Explanation: </strong>There&#39;s nothing to delete.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;deeedbbcccbdaa&quot;, k = 3
<strong>Output:</strong> &quot;aa&quot;
<strong>Explanation: 
</strong>First delete &quot;eee&quot; and &quot;ccc&quot;, get &quot;ddbbbdaa&quot;
Then delete &quot;bbb&quot;, get &quot;dddaa&quot;
Finally delete &quot;ddd&quot;, get &quot;aa&quot;</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;pbbcggttciiippooaais&quot;, k = 2
<strong>Output:</strong> &quot;ps&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= k &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> only contains lowercase English letters.</li>
</ul>

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        st = []
        for i in range(len(s)):
            if st and st[-1][0] == s[i]:
                ch,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((ch,cnt))
            else:
                st.append((s[i],1))
        res = ""
        for ch,cnt in st:
            res+=ch*cnt
        return res



















        st = []
        for ch in s:
            if st and st[-1][0] == ch:
                c,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((c,cnt))
            else:
                st.append((ch,1))
        res = ""
        for c,cnt in st:
            res+=c*cnt
        return res












        st = []
        for c in s:
            if st and st[-1][0] == c:
                ch,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((ch,cnt))
            else:
                st.append((c,1))
        res = ""
        for ch,cnt in st:
            res+=ch*cnt
        return res












        st = []
        for ch in s:
            if st and st[-1][0] == ch:
                c,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((c,cnt))
            else:
                st.append((ch,1))
        res = ""
        for ch,cnt in st:
            res+=cnt*ch
        return res












        st = []
        for ch in s:
            if st and st[-1][0] == ch:
                c,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((c,cnt))
            else:
                st.append((ch,1))
        res = ""
        for ch,cnt in st:
            res+=cnt*ch
        return res













        st = []
        for i in range(len(s)):
            if st and st[-1][1] == s[i]:
                cnt,ch = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((cnt,ch))
            else:
                st.append((1,s[i]))
        res = ""
        for n,c in st:
            res +=n*c
        return res 












        st = []
        for ch in s:
            if st and st[-1][0] == ch:
                c,cnt = st.pop()
                cnt+=1
                if cnt < k:
                    st.append((c,cnt))

            else:
                st.append((ch,1))
        res = ""
        for ch,cnt in st:
            res+=cnt*ch
        return res
















        st = []
        for ch in s:
            if st and st[-1][0]==ch:
                char,cnt1 = st.pop()
                cnt1+=1
                if cnt1<k:
                    st.append((char,cnt1))

            else:
                st.append((ch,1))
        res = ""
        for ch,cnt in st:
            res+=cnt*ch
        return res














        st = []
        for i in range(len(s)):
            if st and st[-1][0] == s[i]:
                char,val = st.pop()
                val+=1
                if val<k:
                    st.append((char,val))
            else:
                st.append((s[i],1))
        res = ""
        for c,v in st:
            res+=c*v
        return res
















        st = []
        for i in range(len(s)):
            if st and st[-1][0] == s[i]:
                char,val = st.pop()
                val+=1
                if val<k:
                    st.append((char,val))
            else:
                st.append((s[i],1))
        res = ""
        for ch,v in st:
            res+=ch*v
        return res

















        st = []
        for ch in s:
            if st and st[-1][0] == ch:
                char,val = st.pop()
                val = val+1
                if val<k:
                    st.append((ch,val))
            else:
                st.append((ch,1))
        res = ""
        for ch,val in st:
            res+=ch*val
        return res

















        st = []
        for ch in s:
            if st and ch == st[-1][0]:
                ch,val = st.pop()
                val+=1
                if val <k:
                    st.append((ch,val))
            else:
                st.append((ch,1))
        res = ""
        for ch,char in st:
            res+=ch*char
        return res




















        st = []#(count,ch)
        for ch in s:
            if st and st[-1][0]==ch:
                char,cnt = st.pop()
                cnt+=1
                if cnt<k:
                    st.append((char,cnt))
            else:
                st.append((ch,1))
        res = ""
        for cnt,char in st:
            res+=char*cnt
        return res



















        st = [] #count,char
        for i in range(len(s)):
            if st and st[-1][1] == s[i]:
                cnt,char = st.pop()
                cnt+=1
                if cnt< k:
                    
                
                    # count,char = st.pop()
                    
                    st.append((cnt,char))
            else:
                st.append((1,s[i]))
        res = ""
        for cnt,char in st:
            res+=char*cnt
        return res




















        st = [] #char,count
        for ch in s:

            if st and st[-1][0] == ch:
                ch,cnt = st.pop()
                cnt+=1
                if cnt < k:
                    st.append((ch,cnt))



            else:
                st.append((ch,1))
        res = ""
        for char,count in st:
            res+=(char)*count
        return res























        st = [] #char,cnt

        for i in range(len(s)):
            if st and st[-1][0]==s[i]:
                char,count = st.pop()
                count+=1
                if count<k:
                    st.append((char,count))
                
                    


            else:
                st.append((s[i],1))
        print(st)
        res = ""
        for char,count in st:
            res+=(char)*count
        return res


























        st = [] #char,count

        for ch in s:
            if st and st[-1][0] == ch:
                st[-1][1] +=1
                if k == st[-1][1]:
                    st.pop()
            else:
                st.append([ch,1])
        res = ""
        for ch,count in st:
            res+=count*ch
        return res

























        st = [] #[char,count]

        for ch in s:
            if st and st[-1][0] == ch:
                st[-1][1]+=1
            else:
                st.append([ch,1])
            if st[-1][1]==k:
                st.pop()
        # print(st)
        res = ""
        for ch,count in st:
            res+=(count*ch)
        return res



























        stack = []  # [char, count]

        for c in s:
            if stack and stack[-1][0] == c:
                stack[-1][1] += 1
            else:
                stack.append([c, 1])

            if stack[-1][1] == k:
                stack.pop()

        res = ""
        for char, count in stack:
            res += char * count

        return res
                
            

            

20900