LeetCode 1209 - Remove All Adjacent Duplicates in String II

LeetCode Problem 1209

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem asks us to repeatedly remove groups of exactly k adjacent identical characters from a string until no more such groups exist.

A removal operation works as follows:

• Find k consecutive characters that are all the same.
• Remove those characters from the string.
• Concatenate the remaining left and right parts together.
• Continue checking again because new adjacent groups may form after the removal.

The important detail is that removals can create new opportunities for future removals. Because of this, we cannot simply scan the string once and delete groups independently.

For example, in:

"deeedbbcccbdaa", k = 3

Removing "eee" creates:

"ddbbcccbdaa"

Then removing "ccc" creates:

"ddbbbdaa"

Now "bbb" becomes removable, and after that "ddd" also becomes removable.

The input consists of:

• A string s containing lowercase English letters
• An integer k representing how many adjacent equal characters are needed for removal

The output is the final string after all possible removals have been performed.

The constraints are important:

• s.length can be as large as 100000
• k can be as large as 10000

These constraints immediately rule out inefficient repeated rescanning approaches. A solution with quadratic complexity would likely time out for the largest inputs.

The problem also guarantees that the final answer is unique. This means the order in which removals are conceptually performed does not affect the final result.

Several edge cases are important to consider:

• Strings with no removable groups
• Strings where removals trigger cascading removals
• Strings where the entire string disappears
• Very long runs of the same character
• k = 2, which creates frequent removals
• Cases where removals occur at the boundary between previously separated segments

A correct solution must efficiently maintain adjacency information as characters are processed.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly scan the string looking for groups of k adjacent equal characters.

One way to implement this is:

1. Scan the string from left to right.
2. Count consecutive identical characters.
3. When a count reaches k, remove those characters.
4. Restart scanning because the removal may create new removable groups.

This approach is correct because it explicitly simulates the problem statement. Every time a valid group appears, it is removed, and the process continues until no more removals are possible.

However, this approach is inefficient. Each removal may require rebuilding the string, and after every modification we may need to rescan the entire string again.

In the worst case, this leads to quadratic complexity.

For example:

s = "aaaaaaaaaa...."

Repeated removals force many rescans and repeated string copying operations.

With input size up to 100000, this is too slow.

Optimal Approach

The key observation is that we only care about consecutive character groups and their counts.

A stack is a natural fit because:

• Characters are processed left to right
• Only the most recent group can interact with the current character
• After a removal, the previous group becomes adjacent automatically

Instead of storing every individual character independently, we store:

(character, count)

For each character:

• If it matches the top stack character, increment the count.
• If the count becomes k, remove the group immediately.
• Otherwise, push a new group onto the stack.

This efficiently simulates all cascading removals in a single pass.

Because each character is pushed and popped at most once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated rescanning and rebuilding of the string
Optimal	O(n)	O(n)	Stack tracks character groups and counts efficiently

Algorithm Walkthrough

Step 1: Initialize a Stack

Create an empty stack where each element stores:

(character, frequency)

The stack represents the current compressed state of the string after all removals processed so far.

Step 2: Process Characters Left to Right

Iterate through each character in the string.

For each character:

• If the stack is empty, start a new group.
• If the current character matches the top stack character, increment the count.
• Otherwise, push a new (character, 1) pair.

This groups consecutive identical characters together naturally.

Step 3: Remove Groups When Count Reaches k

After incrementing a count:

• If the count becomes exactly k, pop the stack.

This simulates removing those characters from the string.

The important insight is that popping automatically reconnects the surrounding groups, which matches the problem behavior perfectly.

Step 4: Continue Processing

Keep processing the remaining characters.

Because removals happen immediately, cascading removals are handled naturally without rescanning.

Step 5: Reconstruct the Final String

After processing all characters:

• Each stack entry contains a character and its remaining frequency.
• Repeat each character according to its count.
• Concatenate all groups together.

This produces the final string.

Why it works

The stack always represents the fully reduced form of the processed prefix of the string.

Whenever a character is processed, it either extends the most recent group or starts a new one. If a group reaches size k, removing it immediately is safe because the problem guarantees removals can happen whenever such a group exists.

Since every possible removal is performed as soon as it becomes available, the stack invariant remains correct throughout processing. By the end, the stack contains exactly the final reduced string.

Python Solution

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

        for char in s:
            if stack and stack[-1][0] == char:
                stack[-1][1] += 1

                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([char, 1])

        result = []

        for char, count in stack:
            result.append(char * count)

        return "".join(result)

The implementation uses a stack where each element stores:

[character, count]

As we iterate through the string, we compare the current character with the top of the stack.

If the characters match, we increment the count because the consecutive group has grown. If the count reaches k, we remove the group immediately using pop().

If the character does not match the top stack entry, we start a new group with count 1.

After processing all characters, the stack contains only the remaining groups that were never removed. We reconstruct the final string by repeating each character according to its stored count.

The implementation is efficient because each character participates in at most one push and one pop operation.

Go Solution

func removeDuplicates(s string, k int) string {
	type Pair struct {
		char  byte
		count int
	}

	stack := []Pair{}

	for i := 0; i < len(s); i++ {
		char := s[i]

		if len(stack) > 0 && stack[len(stack)-1].char == char {
			stack[len(stack)-1].count++

			if stack[len(stack)-1].count == k {
				stack = stack[:len(stack)-1]
			}
		} else {
			stack = append(stack, Pair{char, 1})
		}
	}

	result := make([]byte, 0)

	for _, pair := range stack {
		for i := 0; i < pair.count; i++ {
			result = append(result, pair.char)
		}
	}

	return string(result)
}

The Go implementation follows the same logic as the Python version but uses a struct to store character-count pairs.

Slices are used as stacks. Removing the top element is done with:

stack = stack[:len(stack)-1]

The final string is built using a byte slice for efficiency since the input contains only lowercase English letters.

Unlike Python strings, Go strings are immutable, so building the result incrementally with a byte slice avoids repeated allocations.

Worked Examples

Example 1

s = "abcd", k = 2

No adjacent duplicates exist.

Character	Stack State
a	[(a,1)]
b	[(a,1),(b,1)]
c	[(a,1),(b,1),(c,1)]
d	[(a,1),(b,1),(c,1),(d,1)]

Final string:

"abcd"

Example 2

s = "deeedbbcccbdaa", k = 3

Character	Action	Stack State
d	push	[(d,1)]
e	push	[(d,1),(e,1)]
e	increment	[(d,1),(e,2)]
e	reaches 3, remove	[(d,1)]
d	increment	[(d,2)]
b	push	[(d,2),(b,1)]
b	increment	[(d,2),(b,2)]
c	push	[(d,2),(b,2),(c,1)]
c	increment	[(d,2),(b,2),(c,2)]
c	reaches 3, remove	[(d,2),(b,2)]
b	increment	[(d,2),(b,3)]
b	reaches 3, remove	[(d,2)]
d	increment	[(d,3)]
d	reaches 3, remove	[]
a	push	[(a,1)]
a	increment	[(a,2)]

Final string:

"aa"

Example 3

s = "pbbcggttciiippooaais", k = 2

Character	Stack State
p	[(p,1)]
b	[(p,1),(b,1)]
b	[(p,1)]
c	[(p,1),(c,1)]
g	[(p,1),(c,1),(g,1)]
g	[(p,1),(c,1)]
t	[(p,1),(c,1),(t,1)]
t	[(p,1),(c,1)]
c	[(p,1)]
i	[(p,1),(i,1)]
i	[(p,1),(i,2)]
i	[(p,1)]
p	[(p,2)]
p	[]
o	[(o,1)]
o	[]
a	[(a,1)]
a	[]
i	[(i,1)]
s	[(i,1),(s,1)]

Final result:

"ps"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed and popped at most once
Space	O(n)	The stack may store all characters in the worst case

The algorithm processes the string in a single left to right pass.

Each character contributes to at most one stack insertion and one stack removal. Because no character is revisited after processing, the total amount of work is linear.

The stack may contain all characters if no removals occur, which gives linear auxiliary space usage.

Test Cases

solution = Solution()

assert solution.removeDuplicates("abcd", 2) == "abcd"  # no removals
assert solution.removeDuplicates("deeedbbcccbdaa", 3) == "aa"  # cascading removals
assert solution.removeDuplicates("pbbcggttciiippooaais", 2) == "ps"  # multiple chain reactions

assert solution.removeDuplicates("aaa", 3) == ""  # entire string removed
assert solution.removeDuplicates("aaaa", 2) == ""  # repeated removals
assert solution.removeDuplicates("aabbbacd", 3) == "cd"  # middle removal creates new adjacency

assert solution.removeDuplicates("a", 2) == "a"  # single character
assert solution.removeDuplicates("aa", 2) == ""  # exact match
assert solution.removeDuplicates("baaab", 3) == "bb"  # removal creates new neighbors

assert solution.removeDuplicates("aaaaaaaa", 3) == "aa"  # leftover characters after removals
assert solution.removeDuplicates("abcdddcba", 3) == "abccba"  # one removable group
assert solution.removeDuplicates("yyyzzzaa", 3) == "aa"  # multiple removals

assert solution.removeDuplicates("abcdefghijkl", 2) == "abcdefghijkl"  # no duplicates
assert solution.removeDuplicates("kkkkkkkk", 4) == ""  # repeated exact-sized removals

Test	Why
"abcd", 2	Verifies no removals occur
"deeedbbcccbdaa", 3	Validates cascading removals
"pbbcggttciiippooaais", 2	Tests complex chain reactions
"aaa", 3	Entire string disappears
"aaaa", 2	Multiple consecutive removals
"aabbbacd", 3	Removal changes adjacency
"a", 2	Smallest valid string
"aa", 2	Exact removable group
"baaab", 3	Boundary merge behavior
"aaaaaaaa", 3	Leftover remainder after removals
"abcdddcba", 3	Single removable middle group
"yyyzzzaa", 3	Multiple independent removals
"abcdefghijkl", 2	Worst case with no removals
"kkkkkkkk", 4	Repeated exact-sized groups

Edge Cases

One important edge case occurs when the entire string gets removed. For example:

s = "aaa", k = 3

A buggy implementation might leave an empty stack unhandled or incorrectly return None. The stack-based solution handles this naturally because the group is popped once its count reaches k, leaving an empty stack that reconstructs into an empty string.

Another important case is cascading removals. Consider:

s = "deeedbbcccbdaa", k = 3

Removing one group creates new adjacent groups that also become removable. Naive implementations sometimes fail because they only process each position once. The stack solution handles cascading behavior automatically because removals immediately expose the previous group at the stack top.

A third tricky case involves leftover characters after multiple removals. For example:

s = "aaaaaaaa", k = 3

The first six characters are removed in two groups of three, but two characters remain. Incorrect implementations may accidentally remove all characters or mishandle remainder counts. The stack correctly tracks exact frequencies, so only complete groups of size k are removed.

Another subtle case occurs when removals happen at boundaries between groups. In:

s = "baaab", k = 3

Removing "aaa" leaves "bb". The implementation handles this correctly because the stack naturally reconnects previously separated groups after a pop operation.