[LeetCode] 1209 | Remove All Adjacent Duplicates in String II | Python

---

문제 링크: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

---

문제

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.

---

조건

• 1 <= s.length <= $10^5$
• 2 <= k <= $10^4$
• s only contains lower case English letters.

---

내 풀이

s를 차례로 보면서, stack의 마지막 문자가 현재 s의 문자(ch)와 같으면 그 문자의 수를 하나 증가시킨다.

stack의 마지막 문자의 수가 k와 일치하면 그 문자를 삭제한다.

stack의 마지막 문자가 현재 s의 문자(ch)와 같지 않으면 현재 문자를 stack에 추가한다.

---

코드

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