1209. Remove All Adjacent Duplicates In String II - Explanation

Description

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 <= 100,000
2 <= k <= 10,000
s only contains lowercase English letters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The most direct approach is to repeatedly scan the string looking for k consecutive identical characters. When found, we remove them and restart the scan from the beginning since the removal might create new groups of k adjacent duplicates.

This process continues until a full scan completes without finding any group to remove. While straightforward, this approach is inefficient because each removal requires rescanning from the start.

Algorithm

Convert the string to a mutable format (list or character array).
Repeatedly scan the string:
- Track the current character and count consecutive occurrences.
- When the count reaches k, remove those characters from the string, set a flag, and restart the scan.
If a full scan completes without any removal, exit the loop.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        while s:
            flag = False
            cur = s[0]
            cnt = 1
            for i in range(1, len(s)):
                if cur != s[i]:
                    cnt = 0
                    cur = s[i]
                cnt += 1
                if cnt == k:
                    s = s[:i - cnt + 1] + s[i + 1:]
                    flag = True
                    break

            if not flag:
                break

        return s

Time & Space Complexity

Time complexity: $O(\frac {n ^ 2}{k})$
Space complexity: $O(n)$

2. Stack

Intuition

To avoid rescanning the entire string after each removal, we can use a stack to track consecutive counts as we process each character. When we encounter a character, we check if it matches the previous one. If so, we increment the count; otherwise, we start a new count.

When the count reaches k, we remove those k characters and continue from where we left off. The stack helps us remember the count before the removal so we can correctly continue counting if the characters before and after the removed segment match.

Algorithm

Convert the string to a mutable list and initialize an empty stack to track counts.
Iterate through the string with an index i:
- If the current character differs from the previous, push 1 onto the stack.
- If it matches, increment the top of the stack.
- If the count reaches k, pop from the stack, delete those k characters, and adjust the index.
Continue until the end of the string.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        n = len(s)
        i = 0
        s = list(s)

        while i < n:
            if i == 0 or s[i] != s[i - 1]:
                stack.append(1)
            else:
                stack[-1] += 1
                if stack[-1] == k:
                    stack.pop()
                    del s[i - k + 1:i + 1]
                    i -= k
                    n -= k

            i += 1

        return ''.join(s)

Time & Space Complexity

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

3. Stack (Optimal)

Intuition

Instead of modifying the string and tracking counts separately, we can store both the character and its count together in the stack. This eliminates the need for in-place string manipulation and index adjustments.

Each stack entry is a pair of (character, count). When we encounter a new character, we either increment the count of the top entry (if it matches) or push a new entry. When a count reaches k, we simply pop that entry. Building the result at the end involves expanding each entry back into its characters.

Algorithm

Initialize a stack where each entry stores a character and its consecutive count.
For each character in the string:
- If the stack is non-empty and the top character matches, increment its count.
- Otherwise, push a new entry with count 1.
- If the count reaches k, pop the entry from the stack.
Build the result by expanding each stack entry: repeat each character by its count.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # [char, count]

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

        return ''.join(char * count for char, count in stack)

Time & Space Complexity

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

4. Two Pointers

Intuition

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.

Algorithm

Convert the string to a mutable character array and create a count array of the same size.
Use two pointers: j iterates through the original string, i tracks the write position.
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.
Return the substring from 0 to i.

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])

Time & Space Complexity

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

Common Pitfalls

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.