Skip to content

Latest commit

 

History

History
86 lines (59 loc) · 2.12 KB

_1209. Remove All Adjacent Duplicates in String II.md

File metadata and controls

86 lines (59 loc) · 2.12 KB

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top


First completed : June 19, 2024

Last updated : June 19, 2024


Related Topics : String, Stack

Acceptance Rate : 58.93 %


Solutions

Python

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []    # (letter, count)

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

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

        return ''.join([x[0] * x[1] for x in stk])
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []    # (letter, count)
        stkAlt = []


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

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


        while stk :
            c, freq = stk.pop()

            if len(stk) >= 1 and c == stk[-1][0] :   # merge
                stk[-1] = (c, stk[-1][1] + freq)
                continue
            
            if freq % k == 0 :                       # remove all substrs
                if stkAlt :
                    stk.append(stkAlt.pop())
                continue

            if freq > k :                            # remove parts above
                stk.append((c, freq % k))
                continue
            
            stkAlt.append((c, freq))
            
        stk, stkAlt = stkAlt, stk

        return ''.join([x[0] * x[1] for x in reversed(stk)])