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. For example: Input: s = "abcd", k = 2. Output: "abcd" because there's nothing to delete. Another example: Input: s = "deeedbbcccbdaa", k = 3. Output: "aa". The explanation is First delete "eee" and "ccc", get "ddbbbdaa". Then delete "bbb", get "dddaa". Finally delete "ddd", get "aa"

## Solution to Remove All Adjacent Duplicates in String II

This problem requires us to remove adjacent duplicate characters from a string `s` where `k` adjacent characters are the same. We need to repeatedly perform this removal until no more removals can be made.

### 1. Naive Approach (Brute Force)

One straightforward approach is to iterate through the string and, for each character, check if there are `k-1` identical adjacent characters. If so, remove those `k` characters and repeat the process until no more such removals can be made.

```python
def remove_duplicates_naive(s: str, k: int) -> str:
    while True:
        removed = False
        i = 0
        while i < len(s):
            count = 1
            j = i + 1
            while j < len(s) and s[i] == s[j]:
                count += 1
                j += 1

            if count >= k:
                s = s[:i] + s[i + k:]  # Remove k duplicates
                removed = True
                break  # Restart from the beginning
            else:
                i = j

        if not removed:
            break
    return s

Explanation:

This naive approach continuously scans the string, looking for sequences of k identical characters. If it finds one, it removes the sequence and restarts the scan. This repeats until no such sequence is found.

2. Optimal Solution (Using Stack)

A more efficient solution uses a stack to keep track of the characters and their counts. When we encounter a character, we either increment its count on the stack (if it's the same as the top of the stack) or push a new character-count pair onto the stack. When the count reaches k, we pop the character from the stack.

def remove_duplicates_stack(s: str, k: int) -> str:
    stack = []  # Stack of (char, count) pairs

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

    result = "".join(c * count for c, count in stack)
    return result

Explanation:

• We use a stack to store pairs of characters and their consecutive counts.
• For each character in the input string:
  • If the stack is not empty and the current character is the same as the character at the top of the stack, we increment the count of the top element.
  • If the count becomes equal to k, we pop the element from the stack.
  • Otherwise, we push a new pair with a count of 1 onto the stack.
• Finally, we reconstruct the string from the remaining characters and counts in the stack.

3. Big(O) Run-time Analysis

Naive Approach:

• In the worst case, the naive solution might iterate through the string multiple times. If the string is of length n and we potentially remove characters from almost every position, we would need to iterate at most n times through the string. Each iteration takes O(n) time, leading to a run time of O(n^2).

Stack Approach:

• The stack-based approach processes each character in the string exactly once. Pushing and popping from the stack take O(1) time. Therefore, the overall run time is O(n), where n is the length of the string.

4. Big(O) Space Usage Analysis

Naive Approach:

• The space complexity is O(1) because the operations are performed in-place without using extra space that scales with the input size.

Stack Approach:

• In the worst case, the stack might contain all the characters from the string (if there are no duplicates to remove). Thus, the space complexity is O(n), where n is the length of the string.

5. Edge Cases

• Empty String: If the input string s is empty, both solutions will correctly return an empty string.
• k = 1: If k is 1, then all characters are duplicates and should be removed, resulting in an empty string.
• No Duplicates: If the string contains no duplicates, then both algorithms should return the original string.
• Large k: If k is larger than the length of any sequence of identical characters, then the string remains unchanged.

Here's an example of edge case handling in the stack solution:

def remove_duplicates_stack_edge_cases(s: str, k: int) -> str:
    if k == 1:
        return ""  # Remove all characters if k is 1

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

    result = "".join(c * count for c, count in stack)
    return result