Coding Interview PatternsRemove All Adjacent Duplicates in String II
MediumStacks
Remove All Adjacent Duplicates in String II
Explanation & Solution
Description
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.
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There are no adjacent duplicates to remove.
Constraints
1 <= s.length <= 10^52 <= k <= 10^4sonly contains lowercase English letters
Approach
Stacks pattern
1. Stack of Character-Count Pairs
- Each stack entry stores
{char, count}— the character and how many consecutive times it appears
2. Process Each Character
- If the current character matches the top of the stack, increment the count
- Otherwise, push a new entry with count 1
3. Remove k Duplicates
- When any entry's count reaches
k, pop it from the stack - This automatically handles chain reactions — after removal, the new top might now be adjacent to later characters
4. Build Result
- Reconstruct the string by repeating each character by its count
Key Insight
- Storing counts instead of individual characters avoids the need for repeated scanning
- The stack naturally handles cascading removals — when a group is removed, previously separated characters become adjacent
- Time: O(n), Space: O(n)
Visualization
Input:
[a, b, c, d], k = 2
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
5 steps