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.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack and auxiliary storage.
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.
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Stack-Based Solution | Time Complexity: O(n), where n is the length of the string. |
| In-Place Two-Pointer Technique | Time Complexity: O(n) |
| 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. |
Remove All Adjacent Duplicates in String II - Leetcode 1209 - Python • NeetCode • 60,761 views views
Watch 9 more video solutions →Practice Remove All Adjacent Duplicates in String II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor