Watch 10 video solutions for Remove All Adjacent Duplicates in String II, a medium level problem involving String, Stack. This walkthrough by NeetCode has 60,761 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1052 <= k <= 104s only contains lowercase English letters.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 | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Frequency Tracking | O(n) | O(n) | Best general solution. Easy to implement and clearly models removing duplicate groups. |
| In-Place Two-Pointer Technique | O(n) | O(n) | When optimizing for fewer data structures and simulating a stack directly within the string buffer. |