Remove All Adjacent Duplicates in String II

How it works

This approach uses the input array itself as both the working space and the result, avoiding the need for a separate stack data structure. We use two pointers: j reads through the original string while i writes the result.

A separate count array tracks consecutive occurrences at each write position. When we write a character, we check if it matches the previous written character to determine its count. If the count reaches k, we "rewind" the write pointer by k positions, effectively removing those characters.

Steps

1. Convert the string to a mutable character array and create a count array of the same size.
2. Use two pointers: j iterates through the original string, i tracks the write position.
3. For each character at position j:
   • Copy it to position i.
   • Set its count to 1. If the previous character (at i-1) is the same, add the previous count to the current count.
   • If the count reaches k, move i back by k positions.
   • Increment i.
4. Return the substring from 0 to i.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Not Continuing After Removal Creates New Groups

After removing k adjacent duplicates, the characters before and after the removed section may now be adjacent and form a new group of duplicates. A common mistake is stopping after a single removal pass. The solution must continue checking for new groups that may have been created by previous removals.

Resetting Count When Characters Match After Removal

When using a stack-based approach, after removing k characters, the new top of the string may match the next character being processed. Failing to properly inherit or restore the count from before the removal leads to incorrect duplicate detection. The count must reflect the consecutive sequence that existed before the removal.

Off-by-One Errors in Substring Removal

When removing k characters ending at index i, the removal range is from i - k + 1 to i (inclusive). A common bug is using i - k as the start index or forgetting to adjust the current index after removal. Both the string length and the iteration index must be updated correctly to avoid processing removed characters or skipping valid ones.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        i = 0
        n = len(s)
        count = [0] * n
        s = list(s)
        for j in range(n):
            s[i] = s[j]
            count[i] = 1
            if i > 0 and s[i - 1] == s[j]:
                count[i] += count[i - 1]
            if count[i] == k:
                i -= k
            i += 1
        return ''.join(s[:i])

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int i = 0, n = s.length();
        vector<int> count(n);
        for (int j = 0; j < n; i++, j++) {
            s[i] = s[j];
            count[i] = 1;
            if (i > 0 && s[i - 1] == s[j]) {
                count[i] += count[i - 1];
            }
            if (count[i] == k) i -= k;
        }
        return s.substr(0, i);
    }
};