Remove All Adjacent Duplicates in String II solution and explanation
Google
9 more videos on this problem
Remove All Adjacent Duplicates in String II - Leetcode 1209 - PythonNeetCode · 13:05 · 62K views
Remove All Adjacent Duplicates in String II | Live Coding with Explanation | Leetcode - 1209Algorithms Made Easy · 12:28 · 10K views
Remove All Adjacent Duplicates in String II | Leetcode 1209 | Stack | Day-6Ayushi Sharma · 15:58 · 9K views
Remove All Adjacent Duplicates in String II - LeetCode (Solution & Explanation | JavaScript)shirin setayesh · 7:49 · 2K views
LeetCode 1209. Remove All Adjacent Duplicates in String II Explanation and Solutionhappygirlzt · 9:16 · 2K views
Spotify Coding Interview Question - LeetCode 1209 - Remove All Adjacent Duplicates in String 2AlgoJS · 4:26 · 2K views
Leetcode - Remove All Adjacent Duplicates in String II (Python)Timothy H Chang · 4:40 · 1K views
Remove All Adjacent Duplicates in String II | Leetcode 1209Coding Decoded · 8:53 · 1K views
Remove All Adjacent Duplicates in String II | Leetcode 1209EasyLeetcode · 10:34 · 795 views
Remove All Adjacent Duplicates in String II | Leetcode 1209 | Stack | StringNitesh Nanda · 14:39 · 480 views
The problem
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 <= 104sonly 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.
def removeDuplicates(s: str, k: int) -> str:
stack = []
for char in s:
if stack and stack[-1][0] == char:
stack[-1][1] += 1
else:
stack.append([char, 1])
if stack[-1][1] == k:
stack.pop()
return ''.join(char * cnt for char, cnt in stack)
# Example usage
s = "deeedbbcccbdaa"
k = 3
print(removeDuplicates(s, k)) # Output: "aa"import java.util.Stack;
public class Solution {
public String removeDuplicates(String s, int k) {
Stack<int[]> count = new Stack<>();
StringBuilder sb = new StringBuilder();
for (char ch : s.toCharArray()) {
if (!sb.isEmpty() && sb.charAt(sb.length() - 1) == ch) {
count.peek()[0]++;
} else {
sb.append(ch);
count.push(new int[]{1});
}
if (count.peek()[0] == k) {
sb.delete(sb.length() - k, sb.length());
count.pop();
}
}
return sb.toString();
}
}
class Main {
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.removeDuplicates("deeedbbcccbdaa", 3)); // Output: aa
}
}#include <iostream>
#include <string>
#include <vector>
std::string removeDuplicates(const std::string& s, int k) {
std::string result;
std::vector<int> count;
for (char ch : s) {
if (!result.empty() && result.back() == ch) {
count.back()++;
} else {
result.push_back(ch);
count.push_back(1);
}
if (count.back() == k) {
result.erase(result.size() - k);
count.pop_back();
}
}
return result;
}
int main() {
std::string s = "deeedbbcccbdaa";
int k = 3;
std::cout << removeDuplicates(s, k) << std::endl;
return 0;
}function removeDuplicates(s, k) {
const stack = [];
for (const char of s) {
if (stack.length && stack[stack.length - 1][0] === char) {
stack[stack.length - 1][1] += 1;
} else {
stack.push([char, 1]);
}
if (stack[stack.length - 1][1] === k) {
stack.pop();
}
}
return stack.map(pair => pair[0].repeat(pair[1])).join('');
}
// Example usage:
console.log(removeDuplicates("deeedbbcccbdaa", 3)); // "aa"#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* removeDuplicates(char* s, int k) {
int len = strlen(s), top = 0;
char *res = (char *)malloc((len + 1) * sizeof(char));
int *count = (int *)malloc(len * sizeof(int));
for (int i = 0; i < len; i++) {
if (top != 0 && res[top - 1] == s[i]) {
count[top - 1]++;
} else {
res[top] = s[i];
count[top] = 1;
top++;
}
if (count[top - 1] == k) {
top--;
}
}
res[top] = '\0';
free(count);
return res;
}
int main() {
char s[] = "deeedbbcccbdaa";
int k = 3;
char *result = removeDuplicates(s, k);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public string RemoveDuplicates(string s, int k) {
Stack<int> counts = new Stack<int>();
StringBuilder sb = new StringBuilder();
foreach (char c in s) {
if (sb.Length > 0 && sb[sb.Length - 1] == c) {
int newCount = counts.Pop() + 1;
if (newCount == k) {
sb.Length -= k - 1;
} else {
counts.Push(newCount);
}
} else {
sb.Append(c);
counts.Push(1);
}
}
return sb.ToString();
}
public static void Main(string[] args) {
var solution = new Solution();
Console.WriteLine(solution.RemoveDuplicates("deeedbbcccbdaa", 3)); // Output: aa
}
}This Python solution uses a list to simulate a stack, where each element is a tuple containing the character and its current count. If the count reaches k, the character is popped from the stack.
Time Complexity: O(n)
Space Complexity: O(n)
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.
def removeDuplicates(s: str, k: int) -> str:
stack = list(s)
count = [0] * len(s)
j = 0
for i in range(len(s)):
stack[j] = stack[i]
count[j] = count[j - 1] + 1 if j > 0 and stack[j] == stack[j - 1] else 1
if count[j] == k:
j -= k
j += 1
return ''.join(stack[:j])
# Example usage
s = "deeedbbcccbdaa"
k = 3
print(removeDuplicates(s, k))public class Solution {
public String removeDuplicates(String s, int k) {
char[] stack = s.toCharArray();
int[] count = new int[s.length()];
int j = 0;
for (int i = 0; i < s.length(); i++, j++) {
stack[j] = stack[i];
count[j] = (j > 0 && stack[j] == stack[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k) {
j -= k;
}
}
return new String(stack, 0, j);
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.removeDuplicates("deeedbbcccbdaa", 3));
}
}#include <iostream>
#include <string>
std::string removeDuplicates(std::string s, int k) {
int j = 0;
std::vector<int> count(s.size());
for (int i = 0; i < s.size(); ++i) {
s[j] = s[i];
count[j] = (j > 0 && s[j] == s[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k) {
j -= k;
}
++j;
}
return s.substr(0, j);
}
int main() {
std::string s = "deeedbbcccbdaa";
int k = 3;
std::cout << removeDuplicates(s, k) << std::endl;
return 0;
}function removeDuplicates(s, k) {
const stack = s.split('');
const count = new Array(s.length).fill(0);
let j = 0;
for (let i = 0; i < s.length; i++, j++) {
stack[j] = stack[i];
count[j] = (j > 0 && stack[j] === stack[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] === k) {
j -= k;
}
}
return stack.slice(0, j).join('');
}
// Example usage:
console.log(removeDuplicates("deeedbbcccbdaa", 3));#include <stdio.h>
#include <string.h>
char* removeDuplicates(char* s, int k) {
int length = strlen(s);
int count[length];
int j = 0;
for (int i = 0; i < length; ++i) {
s[j] = s[i];
count[j] = (j > 0 && s[j] == s[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k)
j -= k;
++j;
}
s[j] = '\0';
return s;
}
int main() {
char s[] = "deeedbbcccbdaa";
int k = 3;
printf("%s\n", removeDuplicates(s, k));
return 0;
}using System;
using System.Text;
public class Solution {
public string RemoveDuplicates(string s, int k) {
char[] stack = s.ToCharArray();
int[] count = new int[s.Length];
int j = 0;
for (int i = 0; i < s.Length; i++, j++) {
stack[j] = stack[i];
count[j] = (j > 0 && stack[j] == stack[j - 1]) ? count[j - 1] + 1 : 1;
if (count[j] == k) {
j -= k;
}
}
return new string(stack, 0, j);
}
public static void Main(string[] args) {
var solution = new Solution();
Console.WriteLine(solution.RemoveDuplicates("deeedbbcccbdaa", 3));
}
}This Python solution modifies the string in-place as much as possible. The characters are adjusted in a list and only the resulting string part up to the valid index j is considered for output.
Time Complexity: O(n)
Space Complexity: O(n)
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.
func removeDuplicates(s string, k int) string {
stk := []pair{}
for _, c := range s {
if len(stk) > 0 && stk[len(stk)-1].c == c {
stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
if stk[len(stk)-1].v == 0 {
stk = stk[:len(stk)-1]
}
} else {
stk = append(stk, pair{c, 1})
}
}
ans := []rune{}
for _, e := range stk {
for i := 0; i < e.v; i++ {
ans = append(ans, e.c)
}
}
return string(ans)
}
type pair struct {
c rune
v int
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Solution | Time Complexity: O(n) |
| In-Place Two-Pointer Technique | Time Complexity: O(n) |
| Stack | – |
Complexity analysis
| 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. |
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.