# Remove All Adjacent Duplicates in String II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii)
Canonical: https://scaleengineer.com/dsa/problems/remove-all-adjacent-duplicates-in-string-ii
**Data structures:** String, Stack
**Companies:** [Disney](https://scaleengineer.com/companies/disney), [Grammarly](https://scaleengineer.com/companies/grammarly), [Attentive](https://scaleengineer.com/companies/attentive), [FactSet](https://scaleengineer.com/companies/factset)
---
## Problem
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"

**Constraints:**

* `1 <= s.length <= 105`
* `2 <= k <= 104`
* `s` only contains lowercase English letters.

# Approaches
## Brute Force with Repeated Scanning
This approach directly simulates the process described in the problem. It repeatedly scans the string, and whenever it finds a sequence of `k` identical adjacent characters, it removes them. The process is repeated until a full scan of the string finds no such sequences. While straightforward to understand, this method is very inefficient because each removal may require re-scanning the entire string from the beginning.
**Time:** O(N^2 / k). In the worst-case scenario, we might perform O(N/k) removal operations. Each removal and subsequent scan costs O(N), leading to a quadratic time complexity. For a small `k`, this approaches O(N^2). · **Space:** O(N), where N is the length of the string. This space is used to hold the `StringBuilder`.
**Pros:** Simple to conceptualize and implement.
**Cons:** Highly inefficient due to repeated scanning of the string.; String/StringBuilder deletion is an O(N) operation, leading to poor overall performance.; Will result in a 'Time Limit Exceeded' error on large inputs.
### Explanation
We use a `StringBuilder` to allow for efficient character removal compared to immutable `String` objects. The main logic is wrapped in a `while` loop that continues as long as we can find and remove duplicates. In each iteration of this loop, we scan the string. If we find `k` adjacent, identical characters, we remove them and restart the scan. If we complete a full scan without any removals, the string is in its final state, and we can terminate.

```java
class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder sb = new StringBuilder(s);
        boolean changedInPass = true;

        while (changedInPass) {
            changedInPass = false;
            for (int i = 0; i + k <= sb.length(); i++) {
                char currentChar = sb.charAt(i);
                boolean allSame = true;
                for (int j = 1; j < k; j++) {
                    if (sb.charAt(i + j) != currentChar) {
                        allSame = false;
                        break;
                    }
                }

                if (allSame) {
                    sb.delete(i, i + k);
                    changedInPass = true;
                    // A removal might create a new duplicate group at the join point,
                    // so we must restart the scan.
                    break; 
                }
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Convert the input string `s` into a `StringBuilder` for efficient modifications.
- Enter a loop that continues as long as removals are being made in a pass.
- Inside the loop, set a flag, say `foundDuplicates`, to `false`.
- Iterate through the `StringBuilder` from left to right.
- At each position, check if the next `k` characters are identical.
- If they are, delete that substring of length `k` from the `StringBuilder`.
- Set `foundDuplicates` to `true` and break the inner loop to restart the scan from the beginning of the modified string.
- If the inner loop completes without finding any duplicates to remove (`foundDuplicates` remains `false`), exit the outer loop.
- Return the final string from the `StringBuilder`.

## Stack with Character Counts
A more efficient approach is to process the string in a single pass using a stack. The stack can be used to store the characters of the string being built, along with the counts of their consecutive occurrences. When a character is processed, it's either added to the stack or it increments the count of the character at the top of the stack. If a count reaches `k`, that element is popped from the stack, effectively removing the adjacent duplicates. This correctly handles cascading removals, like in `"abbcccbdaa"` where removing `"ccc"` creates a new group `"bbb"`.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and stack operations are amortized O(1). Building the final string also takes O(N) time. · **Space:** O(N). In the worst case (a string with no k-duplicates), the stack could store up to N entries.
**Pros:** Efficient O(N) time complexity.; Handles all cases, including cascading removals, correctly in a single pass.; The logic is relatively clean and easy to follow.
**Cons:** Requires O(N) extra space for the stack.; Requires a final pass to build the string from the stack's contents.
### Explanation
We can use a `Stack` to store pairs of characters and their consecutive counts. A simple helper class or an `int[]` can represent this pair. As we iterate through the input string, we look at the top of the stack. If the current character matches, we increment the count. If it's a new character, we push it with a count of 1. If any character's count reaches `k`, we pop it from the stack. This simulates the removal process in linear time. Finally, we construct the result string from the remaining elements in the stack.

```java
import java.util.Stack;

class Solution {
    // Using a helper class for clarity, but an int[] or two separate stacks would also work.
    private class Pair {
        char character;
        int count;
        Pair(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }

    public String removeDuplicates(String s, int k) {
        Stack<Pair> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (stack.isEmpty() || stack.peek().character != c) {
                stack.push(new Pair(c, 1));
            } else {
                stack.peek().count++;
            }

            if (stack.peek().count == k) {
                stack.pop();
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Pair p : stack) { // Note: Iterating a stack from bottom to top
            for (int i = 0; i < p.count; i++) {
                sb.append(p.character);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Initialize a stack. The stack will store pairs of `(character, count)`.
- Iterate through each character `c` of the input string `s`.
- If the stack is empty or the character `c` is different from the character at the top of the stack, push a new pair `(c, 1)` onto the stack.
- If `c` is the same as the character at the top of the stack, increment the count of the top element.
- After modifying the top element's count, check if its count has reached `k`. If it has, pop the element from the stack, as this group of `k` duplicates is now removed.
- After iterating through the entire string, the stack contains the characters and counts of the final string.
- Build the result string by iterating through the stack and appending each character the number of times indicated by its count.

## Two Pointers (In-place Stack Simulation)
This approach optimizes the stack-based solution by simulating the stack in-place. It uses a two-pointer technique. A fast pointer `j` iterates through the original string, and a slow pointer `i` acts as the top of an implicit stack within the character array itself. An auxiliary array is used to keep track of the counts, mirroring the logic of the stack approach. This method avoids the overhead of stack object management and the final string construction step, potentially offering a slight performance improvement.
**Time:** O(N). A single pass is made through the string. · **Space:** O(N). An auxiliary array of size N is required to store the counts. The character array is modified in-place.
**Pros:** Optimal O(N) time complexity.; Slightly more space-efficient and potentially faster in practice than the explicit stack approach due to avoiding object overhead and the final string-building loop.
**Cons:** Still requires O(N) auxiliary space for the counts array.; The in-place modification of the character array can be slightly less intuitive than the explicit stack.
### Explanation
We use a slow pointer `i` as the write-head and a fast pointer `j` as the read-head. The character array `res` (initialized from `s`) serves as our character 'stack', and a separate `count` array stores the consecutive character counts. As `j` scans through the string, we place characters at `res[i]`. We update `count[i]` based on the previous character `res[i-1]`. If `count[i]` reaches `k`, we effectively 'pop' `k` elements by moving the slow pointer `i` back by `k`. This modifies the array in-place, and the final result is the prefix of the array of length `i`.

```java
class Solution {
    public String removeDuplicates(String s, int k) {
        int i = 0; // slow pointer, acts as stack top
        int n = s.length();
        char[] res = s.toCharArray();
        int[] count = new int[n];

        for (int j = 0; j < n; j++) { // fast pointer
            res[i] = res[j];
            if (i > 0 && res[i] == res[i - 1]) {
                count[i] = count[i - 1] + 1;
            } else {
                count[i] = 1;
            }
            
            if (count[i] == k) {
                // Move the slow pointer back k steps to remove the group.
                i = i - k;
            }
            i++;
        }
        return new String(res, 0, i);
    }
}
```
### Algorithm
- Initialize a character array `res` from the input string `s` and an integer array `count` of the same size.
- Use a slow pointer `i` to track the end of the valid result string (the 'stack top') and a fast pointer `j` to iterate through the input.
- Iterate `j` from `0` to `n-1`:
  - Copy the character from `res[j]` to `res[i]`.
  - Calculate the count for the character at `res[i]`. If `i > 0` and `res[i]` is the same as `res[i-1]`, the new count is `count[i-1] + 1`. Otherwise, it's `1`.
  - Store this count in `count[i]`.
  - If `count[i]` equals `k`, it means a k-duplicate group is formed. Remove it by moving the slow pointer back: `i = i - k`.
- After the loop, `i` will be the length of the final string.
- Return a new string created from the `res` array, from index `0` with length `i`.

# Solutions
### Java

```java
class Solution {
public
  String removeDuplicates(String s, int k) {
    Deque<int[]> stk = new ArrayDeque<>();
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      if (!stk.isEmpty() && stk.peek()[0] == j) {
        stk.peek()[1] = (stk.peek()[1] + 1) % k;
        if (stk.peek()[1] == 0) {
          stk.pop();
        }
      } else {
        stk.push(new int[]{j, 1});
      }
    }
    StringBuilder ans = new StringBuilder();
    for (var e : stk) {
      char c = (char)(e[0] + 'a');
      for (int i = 0; i < e[1]; ++i) {
        ans.append(c);
      }
    }
    ans.reverse();
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string removeDuplicates(string s, int k) {
    vector<pair<char, int>> stk;
    for (char &c : s) {
      if (stk.size() && stk.back().first == c) {
        stk.back().second = (stk.back().second + 1) % k;
        if (stk.back().second == 0) {
          stk.pop_back();
        }
      } else {
        stk.push_back({c, 1});
      }
    }
    string ans;
    for (auto [c, v] : stk) {
      ans += string(v, c);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str: t = [] i, n = 0, len(s) while i < n: j = i while j < n and s[j] == s[i]: j += 1 cnt = j - i cnt %= k if t and t[- 1][0] == s[i]: t[- 1][1] = (t[- 1][1] + cnt) % k if t[- 1][1] == 0: t . pop() elif cnt: t . append([s[i], cnt]) i = j ans = [c * v for c, v in t] return "" . join(ans)

```