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.

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"

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # Use a stack to store characters and their counts
        
        for char in s:
            if stack and stack[-1][0] == char:
                stack[-1][1] += 1  # Increment count if the character matches the top of the stack
                if stack[-1][1] == k:
                    stack.pop()  # Remove if count reaches k
            else:
                stack.append([char, 1])  # Add new character with count 1
        
        result = "" # Build the resulting string
        for char, count in stack:
            result += char * count
        
        return result

Explanation:

The problem requires removing k adjacent and equal characters from a string s repeatedly until no such removals can be made. The solution uses a stack to efficiently track characters and their counts. Here’s a detailed breakdown:

1. Initialization: A stack stack is used to store pairs of characters and their consecutive counts. It processes the input string s character by character.

2. Character Processing: For each character in s:

   • If the stack is not empty and the current character matches the character at the top of the stack, the count of that character at the top of the stack is incremented.
   • If incrementing the count makes it equal to k, the character is removed from the stack (i.e., stack.pop()).
   • If the stack is empty or the current character is different from the one at the top, a new pair [char, 1] is added to the stack.

3. Result Generation: After processing all characters, the stack contains the remaining characters and their counts. The result string is built by concatenating each character repeated by its count.

Example:

Consider the input s = "deeedbbcccbdaa", k = 3.

1. Processing "deeedbbcccbdaa":

   • d is added: stack = [['d', 1]]
   • e is added: stack = [['d', 1], ['e', 1]]
   • e is added: stack = [['d', 1], ['e', 2]]
   • e is added: stack = [['d', 1], ['e', 3]]. e is removed, stack = [['d', 1]]
   • d is added: stack = [['d', 2]]
   • b is added: stack = [['d', 2], ['b', 1]]
   • b is added: stack = [['d', 2], ['b', 2]]
   • b is added: stack = [['d', 2], ['b', 3]]. b is removed, stack = [['d', 2]]
   • c is added: stack = [['d', 2], ['c', 1]]
   • c is added: stack = [['d', 2], ['c', 2]]
   • c is added: stack = [['d', 2], ['c', 3]]. c is removed, stack = [['d', 2]]
   • b is added: stack = [['d', 2], ['b', 1]]
   • d is added: stack = [['d', 2], ['b', 1], ['d', 1]]
   • a is added: stack = [['d', 2], ['b', 1], ['d', 1], ['a', 1]]
   • a is added: stack = [['d', 2], ['b', 1], ['d', 1], ['a', 2]]

2. The final result is constructed: "ddbaa" becomes "aa" after removing ddd

Big O Runtime Analysis:

• Time Complexity: O(n), where n is the length of the string s. Each character is processed once, and stack operations (push and pop) take constant time.

Big O Space Usage Analysis:

• Space Complexity: O(n), where n is the length of the string s. In the worst-case scenario (e.g., "abcabcabc" with k=2), the stack might store all characters of the string.