Remove All Adjacent Duplicates in String II
Problem
Given a string s and an integer k, repeatedly remove k adjacent and equal characters from s until no more such removals are possible, and return the final string.
- 1 ≤ s.length ≤ 10⁵
- 2 ≤ k ≤ 10⁴
- s consists of lowercase English letters.
Example
s = "deeedbbcccbdaa", k = 3"aa"We maintain a stack of pairs (char, count). Each pair represents a compressed run of the current string after all deletions so far. Notation: stack = [(d,1),(e,2)] means the current built string is "dee". Start: stack = [] Read 'd': push (d,1) stack = [(d,1)] Read 'e': push (e,1) stack = [(d,1),(e,1)] Read 'e': increment top to (e,2) stack = [(d,1),(e,2)] Read 'e': increment top to (e,3) => count hits k, pop it stack = [(d,1)] Read 'd': increment top to (d,2) stack = [(d,2)] Read 'b': push (b,1) stack = [(d,2),(b,1)] Read 'b': increment top to (b,2) stack = [(d,2),(b,2)] Read 'c': push (c,1) stack = [(d,2),(b,2),(c,1)] Read 'c': increment top to (c,2) stack = [(d,2),(b,2),(c,2)] Read 'c': increment top to (c,3) => count hits k, pop it stack = [(d,2),(b,2)] Read 'b': increment top to (b,3) => count hits k, pop it stack = [(d,2)] Read 'd': increment top to (d,3) => count hits k, pop it stack = [] Read 'a': push (a,1) stack = [(a,1)] Read 'a': increment top to (a,2) stack = [(a,2)] Reconstruct output by expanding the stack: "a" repeated 2 times => "aa"
Approach
Straightforward Solution
A naive approach would repeatedly scan the string to find k-length groups and remove them, which could lead to O(n^2) or worse time complexity due to repeated rescanning and string rebuilding.
Core Observation
The problem requires removing groups of k identical adjacent characters repeatedly until no such groups remain. This implies a need to track consecutive characters and their counts dynamically as the string is processed.
Path to Optimal
The key insight is to process the string in a single pass using a stack that stores pairs of (character, count). For each character, if it matches the top of the stack, increment the count; otherwise, push a new pair. When the count reaches k, pop the pair from the stack, effectively removing that group. This approach avoids rescanning and achieves linear time complexity.
Optimal Approach
Use a stack to track characters and their consecutive counts. Iterate through the string once, updating counts or pushing new entries. When a count reaches k, pop the stack to remove that group. Finally, reconstruct the string from the stack by repeating each character by its count. This guarantees O(n) time and O(n) space.
Time
O(n)
Each character is processed exactly once. Stack operations (push, pop, increment) are O(1) amortized, so total time is linear in the length of the string.
Space
O(n)
In the worst case, no removals occur and the stack stores all characters with their counts, requiring space proportional to the input size.
Pattern Spotlight
Stack (Count Tracking for Adjacent Removal)
Use a stack to track consecutive character counts, and remove groups immediately when counts reach k, enabling a single-pass linear-time solution without rescanning.
Solution
| 1 | class Solution: |
| 2 | def removeDuplicates(self, s: str, k: int) -> str: |
| 3 | stack = [] |
| 4 | |
| 5 | for c in s: |
| 6 | if stack and stack[-1][0] == c: |
| 7 | stack[-1][1] += 1 |
| 8 | else: |
| 9 | stack.append([c, 1]) |
| 10 | |
| 11 | if stack[-1][1] == k: |
| 12 | stack.pop() |
| 13 | |
| 14 | return ''.join(c * n for c, n in stack) |
Step-by-Step Solution
Track Consecutive Characters and Counts Using a Stack
| 3 | stack = [] |
| 5 | for c in s: |
| 6 | if stack and stack[-1][0] == c: |
| 7 | stack[-1][1] += 1 |
| 8 | else: |
| 9 | stack.append([c, 1]) |
Objective
To maintain a stack that stores pairs of characters and their consecutive counts while iterating through the string.
Key Insight
By storing each character along with how many times it has appeared consecutively, the algorithm can efficiently detect when a group of size k is formed. This avoids rescanning and enables immediate removal by popping the stack. The stack acts as a compressed representation of the string's current state.
Interview Quick-Check
Core Logic
The stack stores pairs [character, count], incrementing count if the current character matches the top, or pushing a new pair otherwise.
State & Boundaries
Check if the stack is non-empty before accessing the top element to avoid errors.
Common Pitfalls & Bugs
Forgetting to handle the empty stack case before comparing characters leads to runtime errors.
Remove Groups When Count Reaches k by Popping the Stack
| 11 | if stack[-1][1] == k: |
| 12 | stack.pop() |
Objective
To detect when a consecutive group reaches size k and remove it immediately by popping the stack.
Key Insight
When the count of the top stack element reaches k, it means a group of k identical adjacent characters has formed and should be removed. Popping the stack removes this group from the current string state. This immediate removal prevents the group from contributing to the final string and avoids the need for further rescanning or complex string manipulation.
Interview Quick-Check
Core Logic
After incrementing the count for a character, check if it equals k; if so, pop the stack to remove the group.
State & Boundaries
Ensure the count check happens after updating the count to catch newly formed groups.
Common Pitfalls & Bugs
Delaying removal or failing to pop immediately leads to incorrect final strings or extra complexity.
Reconstruct the Final String from the Stack
| 14 | return ''.join(c * n for c, n in stack) |
Objective
To build the resulting string by repeating each character in the stack by its count.
Key Insight
After processing the entire input string and removing all k-sized groups, the stack contains the compressed form of the final string. Reconstructing the string by repeating each character by its count restores the correct order and content. This step leverages the stack's maintained state to efficiently produce the output without additional scanning or complex operations.
Interview Quick-Check
Core Logic
Use a generator expression to concatenate each character repeated by its count from the stack.
Complexity
This reconstruction is O(n) time, proportional to the length of the final string.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
stack[-1][1] += 1Increment the count of the top stack element since the current character matches it.
This line is critical because it updates the run-length count in place, enabling immediate detection of groups of size k without rescanning or additional data structures.
if stack[-1][1] == k:Check if the count of the top stack element has reached k.
This check is the pivotal moment where the algorithm decides to remove a group, preventing it from appearing in the final string and enabling a linear-time solution.
stack.pop()Remove the top stack element to delete the group of k characters.
This removal is the core operation that enforces the problem's requirement, enabling the algorithm to maintain a compressed state and avoid costly repeated scans.
stack = []Initialize an empty stack to store pairs of characters and their consecutive counts.
The stack is the core data structure enabling efficient tracking of consecutive characters and their counts, which is essential for detecting and removing k-sized groups in a single pass.
if stack and stack[-1][0] == c:Check if the stack is non-empty and the current character matches the character at the top of the stack.
This condition identifies whether the current character continues a consecutive run, enabling incrementing the count rather than starting a new run.
else:Start a new consecutive group by pushing the current character with count 1 onto the stack.
When the current character differs from the top of the stack or the stack is empty, a new group begins, so a new pair is pushed to track this fresh run.
return ''.join(c * n for c, n in stack)Reconstruct and return the final string by repeating each character in the stack by its count.
This step translates the compressed stack representation back into the final string after all removals, ensuring the output reflects all k-sized group deletions.
stack.append([c, 1])Append the new character-count pair to the stack.
This action records the start of a new consecutive character run, maintaining the stack's invariant of tracking runs.
for c in s:Iterate through each character in the input string s.
Processing characters sequentially allows the algorithm to build and update the stack state dynamically, reflecting the current run-length encoding of the string.
Test Your Understanding
Why does using a stack with counts allow removal of k adjacent duplicates in a single pass without rescanning the string?
Because the stack maintains the current run-length counts of characters, allowing immediate detection and removal of groups of size k as soon as they form, eliminating the need to revisit previous characters.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Remove All Adjacent Duplicates in String II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove All Adjacent Duplicates in String II drill