1209. Remove All Adjacent Duplicates in String II (Python)

Related Topic

Stack.

Description

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.

Sample I/O

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"

Note

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

Methodology

Iterate the string, append the current character and count = 1 to stack if stack empty or top character is not equal to current character. If current character is equal to the top character then top character’s count + 1 and If the count is equal to k, then pop the top from stack. After iteration, there will be only characters which is not satisfied the requirement left. We iterate the stack and concatenate the character to the res string.

def removeDuplicates(self, s: str, k: int) -> str:
        size = len(s)
        if k>size or not k: return s
        stack=[]
        for c in s:
            if stack and stack[-1][0]==c:
                stack[-1][1]+=1
                if stack[-1][1]==k:stack.pop()
                continue
            stack.append([c,1])
        res=''
        for value, count in stack:
            res+=value*count
        return res

BigO

We iterate the string once the time complexity is O(N).