How do you solve Remove All Adjacent Duplicates in String II?

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.

What pattern does Remove All Adjacent Duplicates in String II use?

The Pattern: Stack (Count Tracking for Adjacent Removal) The Heuristic: 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.

Remove All Adjacent Duplicates in String II

Q: What is the time complexity of Remove All Adjacent Duplicates in String II?

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.

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

Input: s = "deeedbbcccbdaa", k = 3

Output: "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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a stack to track characters and their consecutive counts. Iterate through the string once, updating counts or pushing new entries…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def removeDuplicates(self, s: str, k: int) -> str:
      stack = []  
      
      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(c * n for c, n in stack) 

Step-by-Step Solution

1

Track Consecutive Characters and Counts Using a Stack

3stack = []  
5for 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.

2

Remove Groups When Count Reaches k by Popping the Stack

To detect when a consecutive group reaches size k and remove it immediately by popping the stack.

3

Reconstruct the Final String from the Stack

To build the resulting string by repeating each character in the stack by its count.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 7 Critical

stack[-1][1] += 1

Increment 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.

Line 11 Critical

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.

Line 12 Critical

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.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does using a stack with counts allow removal of k adjacent duplicates in a single pass without rescanning the string?

See the answer with Pro.

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

or drill a free problem

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

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