Skip to main content
Talentd

Remove All Adjacent Duplicates in String II - Solution & Explanation

MediumStringStack17 min readAsked at: Amazon, Microsoft, Goldman Sachs +15
Practice this problem

Problem Statement

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 <= 105
  • 2 <= k <= 104
  • s only contains lowercase English letters.

Approach Overview

Problem Overview: Given a string s and an integer k, repeatedly remove groups of k identical adjacent characters. After each removal, new adjacent groups may form, so the process continues until no such group exists. Return the final string.

Approach 1: Stack-Based Solution (O(n) time, O(n) space)

The cleanest way to simulate removals is with a stack that tracks characters and their current consecutive frequency. Iterate through the string once. For each character, check the top of the stack. If it matches, increment the count; otherwise push a new pair (char, count). When the count reaches k, pop that entry from the stack, effectively removing the duplicate group. Because each character is pushed and popped at most once, the algorithm runs in O(n) time with O(n) auxiliary space. This method maps naturally to problems involving collapsing adjacent patterns and is a common pattern with stack processing in string problems.

The key insight: instead of repeatedly deleting substrings (which would be expensive), maintain the run length of each character while scanning the string once. When a run hits k, remove it immediately. This avoids repeated rescanning and keeps the algorithm linear.

Approach 2: In-Place Two-Pointer Technique (O(n) time, O(n) space)

This approach treats the string like a writable array and simulates a stack using two pointers. Maintain a write pointer that builds the resulting string and a separate array tracking the count of consecutive characters. Iterate with a read pointer. Copy the current character to the write index and update the count based on whether it matches the previous character. If the count becomes k, move the write pointer back by k positions, effectively deleting that block. The process continues with the remaining characters.

The benefit of this technique is that it avoids an explicit stack structure while still achieving O(n) time. The array itself behaves like a stack and the write pointer acts as the stack top. This pattern often appears in problems involving in-place string transformations and can be combined with two pointers to maintain linear performance.

Recommended for interviews: The stack-based solution is the most commonly expected answer. It clearly expresses the idea of tracking consecutive character runs and removing them when they reach k. Interviewers usually accept either implementation, but the stack approach communicates the logic faster and is easier to reason about under pressure.

Approach 1: Stack-Based Solution

This approach utilizes a stack data structure to track characters and their counts. As we iterate through the string, we push characters with their current counts on the stack. When the count of the top character in the stack reaches k, we pop the character from the stack to simulate removal of duplicates.

The C solution uses a dynamic character array res to construct the result string, simulating a stack. An auxiliary array count keeps track of the current streak of consecutive characters. When the count reaches k, the top character is removed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack and auxiliary storage.

Try this approach in the editor →

Approach 2: In-Place Two-Pointer Technique

This approach utilizes a two-pointer technique to modify the string in place. Here, we treat the string as a character array, using one pointer to scan the input and another to build the output string. A helper array is used to store counts of consecutive characters.

The C solution employs an extra integer array to keep track of the count of consecutive characters for each position j in the resultant array. Characters are removed in-place by adjusting the index j accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Stack

We can traverse the string s, maintaining a stack that stores the characters and their occurrence counts. When traversing to character c, if the character at the top of the stack is the same as c, we increment the count of the top element by one; otherwise, we push the character c and count 1 into the stack. When the count of the top element equals k, we pop the top element from the stack.

After traversing the string s, the elements remaining in the stack form the final result. We can pop the elements from the stack one by one, concatenate them into a string, and that's our answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Solution

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack and auxiliary storage.

In-Place Two-Pointer Technique

Time Complexity: O(n)
Space Complexity: O(n)

Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based Frequency TrackingO(n)O(n)Best general solution. Easy to implement and clearly models removing duplicate groups.
In-Place Two-Pointer TechniqueO(n)O(n)When optimizing for fewer data structures and simulating a stack directly within the string buffer.

Video Solution

Remove All Adjacent Duplicates in String II - Leetcode 1209 - Python • NeetCode • 62,374 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove All Adjacent Duplicates in String II easy or hard?
The problem is rated Medium because the main challenge is recognizing the need to track consecutive runs efficiently. Once the stack pattern is identified, the implementation becomes straightforward and runs in linear time.
Remove All Adjacent Duplicates in String II Python/Java solution
Most implementations store (character, count) pairs in a stack. In Python, a list works well as the stack, while Java commonly uses an ArrayDeque or custom pair structure. Both implementations process the string in O(n) time.
How to solve Remove All Adjacent Duplicates in String II in O(n)?
Scan the string once while tracking consecutive character counts. Use a stack or an in-place array with a write pointer to store characters and their frequencies. When the count reaches k, remove that block immediately by popping from the stack or rewinding the write pointer.
What is the best approach for Remove All Adjacent Duplicates in String II?
The stack-based approach is the most reliable solution. While scanning the string, store pairs of (character, frequency) on a stack and remove entries when the count reaches k. Each character is processed once, giving O(n) time complexity and O(n) space.
Is Remove All Adjacent Duplicates in String II asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests string processing, stack usage, and linear-time optimization. The problem also evaluates whether candidates can track frequency runs efficiently.
What data structure is used in Remove All Adjacent Duplicates in String II?
A stack is the primary data structure used to track characters and their consecutive counts. Some optimized implementations simulate the stack using arrays and two pointers, but the underlying concept is still stack-based run tracking.
What is the time complexity of Remove All Adjacent Duplicates in String II?
The optimal algorithms run in O(n) time where n is the length of the string. Each character is pushed to and possibly popped from a stack once, so the total number of operations remains linear. Space complexity is typically O(n) for storing intermediate characters.

Ready to solve this problem?

Practice Remove All Adjacent Duplicates in String II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimize String Length

Next

Remove All Adjacent Duplicates In String