Remove All Adjacent Duplicates in String II
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly scans the string, and whenever it finds a sequence of k identical adjacent characters, it removes them. The process is repeated until a full scan of the string finds no such sequences. While straightforward to understand, this method is very inefficient because each removal may require re-scanning the entire string from the beginning.
Algorithm
- Convert the input string
sinto aStringBuilderfor efficient modifications. - Enter a loop that continues as long as removals are being made in a pass.
- Inside the loop, set a flag, say
foundDuplicates, tofalse. - Iterate through the
StringBuilderfrom left to right. - At each position, check if the next
kcharacters are identical. - If they are, delete that substring of length
kfrom theStringBuilder. - Set
foundDuplicatestotrueand break the inner loop to restart the scan from the beginning of the modified string. - If the inner loop completes without finding any duplicates to remove (
foundDuplicatesremainsfalse), exit the outer loop. - Return the final string from the
StringBuilder.
Walkthrough
We use a StringBuilder to allow for efficient character removal compared to immutable String objects. The main logic is wrapped in a while loop that continues as long as we can find and remove duplicates. In each iteration of this loop, we scan the string. If we find k adjacent, identical characters, we remove them and restart the scan. If we complete a full scan without any removals, the string is in its final state, and we can terminate.
class Solution { public String removeDuplicates(String s, int k) { StringBuilder sb = new StringBuilder(s); boolean changedInPass = true; while (changedInPass) { changedInPass = false; for (int i = 0; i + k <= sb.length(); i++) { char currentChar = sb.charAt(i); boolean allSame = true; for (int j = 1; j < k; j++) { if (sb.charAt(i + j) != currentChar) { allSame = false; break; } } if (allSame) { sb.delete(i, i + k); changedInPass = true; // A removal might create a new duplicate group at the join point, // so we must restart the scan. break; } } } return sb.toString(); }}Complexity
Time
O(N^2 / k). In the worst-case scenario, we might perform O(N/k) removal operations. Each removal and subsequent scan costs O(N), leading to a quadratic time complexity. For a small `k`, this approaches O(N^2).
Space
O(N), where N is the length of the string. This space is used to hold the `StringBuilder`.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Highly inefficient due to repeated scanning of the string.
String/StringBuilder deletion is an O(N) operation, leading to poor overall performance.
Will result in a 'Time Limit Exceeded' error on large inputs.
A more efficient approach is to process the string in a single pass using a stack. The stack can be used to store the characters of the string being built, along with the counts of their consecutive occurrences. When a character is processed, it's either added to the stack or it increments the count of the character at the top of the stack. If a count reaches k, that element is popped from the stack, effectively removing the adjacent duplicates. This correctly handles cascading removals, like in "abbcccbdaa" where removing "ccc" creates a new group "bbb".
Algorithm
- Initialize a stack. The stack will store pairs of
(character, count). - Iterate through each character
cof the input strings. - If the stack is empty or the character
cis different from the character at the top of the stack, push a new pair(c, 1)onto the stack. - If
cis the same as the character at the top of the stack, increment the count of the top element. - After modifying the top element's count, check if its count has reached
k. If it has, pop the element from the stack, as this group ofkduplicates is now removed. - After iterating through the entire string, the stack contains the characters and counts of the final string.
- Build the result string by iterating through the stack and appending each character the number of times indicated by its count.
Walkthrough
We can use a Stack to store pairs of characters and their consecutive counts. A simple helper class or an int[] can represent this pair. As we iterate through the input string, we look at the top of the stack. If the current character matches, we increment the count. If it's a new character, we push it with a count of 1. If any character's count reaches k, we pop it from the stack. This simulates the removal process in linear time. Finally, we construct the result string from the remaining elements in the stack.
import java.util.Stack; class Solution { // Using a helper class for clarity, but an int[] or two separate stacks would also work. private class Pair { char character; int count; Pair(char character, int count) { this.character = character; this.count = count; } } public String removeDuplicates(String s, int k) { Stack<Pair> stack = new Stack<>(); for (char c : s.toCharArray()) { if (stack.isEmpty() || stack.peek().character != c) { stack.push(new Pair(c, 1)); } else { stack.peek().count++; } if (stack.peek().count == k) { stack.pop(); } } StringBuilder sb = new StringBuilder(); for (Pair p : stack) { // Note: Iterating a stack from bottom to top for (int i = 0; i < p.count; i++) { sb.append(p.character); } } return sb.toString(); }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once, and stack operations are amortized O(1). Building the final string also takes O(N) time.
Space
O(N). In the worst case (a string with no k-duplicates), the stack could store up to N entries.
Trade-offs
Pros
Efficient O(N) time complexity.
Handles all cases, including cascading removals, correctly in a single pass.
The logic is relatively clean and easy to follow.
Cons
Requires O(N) extra space for the stack.
Requires a final pass to build the string from the stack's contents.
This approach optimizes the stack-based solution by simulating the stack in-place. It uses a two-pointer technique. A fast pointer j iterates through the original string, and a slow pointer i acts as the top of an implicit stack within the character array itself. An auxiliary array is used to keep track of the counts, mirroring the logic of the stack approach. This method avoids the overhead of stack object management and the final string construction step, potentially offering a slight performance improvement.
Algorithm
- Initialize a character array
resfrom the input stringsand an integer arraycountof the same size. - Use a slow pointer
ito track the end of the valid result string (the 'stack top') and a fast pointerjto iterate through the input. - Iterate
jfrom0ton-1:- Copy the character from
res[j]tores[i]. - Calculate the count for the character at
res[i]. Ifi > 0andres[i]is the same asres[i-1], the new count iscount[i-1] + 1. Otherwise, it's1. - Store this count in
count[i]. - If
count[i]equalsk, it means a k-duplicate group is formed. Remove it by moving the slow pointer back:i = i - k.
- Copy the character from
- After the loop,
iwill be the length of the final string. - Return a new string created from the
resarray, from index0with lengthi.
Walkthrough
We use a slow pointer i as the write-head and a fast pointer j as the read-head. The character array res (initialized from s) serves as our character 'stack', and a separate count array stores the consecutive character counts. As j scans through the string, we place characters at res[i]. We update count[i] based on the previous character res[i-1]. If count[i] reaches k, we effectively 'pop' k elements by moving the slow pointer i back by k. This modifies the array in-place, and the final result is the prefix of the array of length i.
class Solution { public String removeDuplicates(String s, int k) { int i = 0; // slow pointer, acts as stack top int n = s.length(); char[] res = s.toCharArray(); int[] count = new int[n]; for (int j = 0; j < n; j++) { // fast pointer res[i] = res[j]; if (i > 0 && res[i] == res[i - 1]) { count[i] = count[i - 1] + 1; } else { count[i] = 1; } if (count[i] == k) { // Move the slow pointer back k steps to remove the group. i = i - k; } i++; } return new String(res, 0, i); }}Complexity
Time
O(N). A single pass is made through the string.
Space
O(N). An auxiliary array of size N is required to store the counts. The character array is modified in-place.
Trade-offs
Pros
Optimal O(N) time complexity.
Slightly more space-efficient and potentially faster in practice than the explicit stack approach due to avoiding object overhead and the final string-building loop.
Cons
Still requires O(N) auxiliary space for the counts array.
The in-place modification of the character array can be slightly less intuitive than the explicit stack.
Solutions
Solution
class Solution {public String removeDuplicates(String s, int k) { Deque<int[]> stk = new ArrayDeque<>(); for (int i = 0; i < s.length(); ++i) { int j = s.charAt(i) - 'a'; if (!stk.isEmpty() && stk.peek()[0] == j) { stk.peek()[1] = (stk.peek()[1] + 1) % k; if (stk.peek()[1] == 0) { stk.pop(); } } else { stk.push(new int[]{j, 1}); } } StringBuilder ans = new StringBuilder(); for (var e : stk) { char c = (char)(e[0] + 'a'); for (int i = 0; i < e[1]; ++i) { ans.append(c); } } ans.reverse(); return ans.toString(); }}class Solution {public: string removeDuplicates(string s, int k) { vector<pair<char, int>> stk; for (char &c : s) { if (stk.size() && stk.back().first == c) { stk.back().second = (stk.back().second + 1) % k; if (stk.back().second == 0) { stk.pop_back(); } } else { stk.push_back({c, 1}); } } string ans; for (auto [c, v] : stk) { ans += string(v, c); } return ans; }};class Solution: def removeDuplicates(self, s: str, k: int) -> str: t = [] i, n = 0, len(s) while i < n: j = i while j < n and s[j] == s[i]: j += 1 cnt = j - i cnt %= k if t and t[- 1][0] == s[i]: t[- 1][1] = (t[- 1][1] + cnt) % k if t[- 1][1] == 0: t . pop() elif cnt: t . append([s[i], cnt]) i = j ans = [c * v for c, v in t] return "" . join(ans)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.