1209. Remove All Adjacent Duplicates in String II
Problem Description
The problem provides us with a string s
and an integer k
. The task is to repetitively remove k
adjacent, identical characters from the string until no further such group of k
identical characters exists. After each removal, the left and right parts of the string are concatenated together. This process of removal is known as a k
duplicate removal. The final string obtained after performing as many k
duplicate removals as possible is the output. It is assured that the outcome obtained is unique for the given input string and integer k
.
Intuition
The solution employs a stack data structure to track groups of identical characters. The stack helps us efficiently manage the groups and their counts without repeatedly scanning the whole string, which would be less efficient.
Here's the step-by-step intuition behind the solution:
- Iterate over each character in the input string.
- For each character
c
, check if the top element of the stack is the same character. If it is, we increment the count associated with that character at the top of the stack. - If the count of the top element becomes equal to
k
after incrementing, it means we have foundk
adjacent identical characters, and we can remove them from the stack (mimicking the removal from the string). - If the stack's top element is not
c
, or if the stack is empty, we push the new characterc
onto the stack with an initial count of one, as it starts a new potential group. - After the iteration is complete, we are left with a stack that contains characters and their respective counts that are less than
k
. The final answer is constructed by repeating the characters in the stack according to their remaining counts. - We return the reconstructed string as the result.
This method leverages the stack's Last-In-First-Out (LIFO) property, allowing us to process characters in a way that mimics the described k
duplicate removal process. In essence, we maintain a running "active" portion of the string, with counts reflecting how many consecutive occurrences of each character there are. When any count reaches k
, we've identified a 'completed' group which we can remove, emulating the removal of k
duplicates in the string itself.
Learn more about Stack patterns.
Solution Approach
The implementation uses a stack which is one of the most suited data structures for problems involving successive pairs or groups of elements with some common characteristics, like consecutive duplicate characters in this case.
Here is how the code works:
-
Initializing the Stack: We begin by initializing an empty list "
stk
" which will serve as our stack. The stack will store sublists where each sublist contains a character and a count of how many times it has occurred consecutively. -
Iterating Over the String: We iterate over each character "
c
" in the string "s
":- Top of the Stack Comparison: We look at the top element of the stack (if it isn't empty) to see if
c
is the same as the character at the top of the stack (stk[-1][0]
represents the character at the top of the stack). - Incrementing Count: If the top element is the same as
c
, we increment the count (stk[-1][1]
) and check if this count has reachedk
. If the count isk
, this signifies ak
duplicate removal, and therefore we pop the top of the stack. - Pushing New Characters: If the stack is empty or
c
is different from the top character of the stack, we push a new sublist onto the stack withc
and the count1
.
- Top of the Stack Comparison: We look at the top element of the stack (if it isn't empty) to see if
-
Reconstructing the String: After the iteration, the stack contains characters that did not qualify for
k
duplicate removal, with their counts being less thank
. Now, to reconstruct the final string, we multiply (*
) each characterc
by its countv
and join ("".join()
) the multiplied strings to form the answer.
The mathematical formula for the reconstruction process is given by:
ans = "".join([c * v for c, v in stk])
Here is the breakdown using the code:
if stk and stk[-1][0] == c:
This checks if the stack is not empty and whether the top element on the stack is the same as the current character.stk[-1][1] = (stk[-1][1] + 1) % k
: Here, we increment the count and use the modulus operator to reset it to0
if it reachesk
(sincek % k
is0
).if stk[-1][1] == 0: stk.pop()
: If after incrementing, the count becomes0
, meaning we havek
duplicates, we remove (pop) the top element from the stack.else: stk.append([c, 1])
: In case the characterc
is different or the stack is empty, we appendc
along with the initial count1
as a new group in the stack.ans = [c * v for c, v in stk]
: We build the answer list by multiplying the characterc
by its countv
.return "".join(ans)
: Join all strings in theans
list to get the final answer.
The code takes advantage of Python's built-in list operations to simulate stack behavior efficiently, making the solution succinct and highly readable.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example and walk through the solution approach to illustrate how it works. Assume s = "aabbbacc"
and k = 3
. Here's how the algorithm would process this:
-
Initializing the Stack: We start with an empty stack
stk
. -
Iterating Over the String:
- We begin to iterate over
s
. First character is'a'
. The stack is empty, so we push['a', 1]
. - Next character is
'a'
. The top of the stack is'a'
, we increment the count:['a', 2]
. - We move to the next character
'b'
. Stack's top is'a'
, which is different, so we push['b', 1]
. - Next is another
'b'
. The top is'b'
with count1
. Increment count:['b', 2]
. - Another
'b'
comes. Increment count:['b', 3]
. But now we've hitk
duplicates, so we remove this from the stack. - The next character is
'a'
. Top of the stack is'a'
with count2
. Increment the count and now we have'a'
with count3
, which meets the removal condition, and thus it is removed from the stack as well. - We then see
'c'
. The stack is empty now, so we push['c', 1]
. - Another
'c'
comes up. Top is'c'
with count1
. Increment count:['c', 2]
.
At the end of this process, our stack
stk
is[ ['c', 2] ]
since we only have two'c'
characters, which is less than thek
duplicate threshold. - We begin to iterate over
-
Reconstructing the String:
- We can't remove any more elements, so it's time to reconstruct the string from the stack items. We multiply each character by its count:
'c' * 2
which yields'cc'
.
- We can't remove any more elements, so it's time to reconstruct the string from the stack items. We multiply each character by its count:
Hence, the final string after performing k
duplicate removals is "cc"
.
Here is the resultant stack operations visualized at each step:
Input | Stack | Operation |
---|---|---|
'a' | [('a', 1)] | Push 'a' |
'a' | [('a', 2)] | Increment count of 'a' |
'b' | [('a', 2), ('b', 1)] | Push 'b' |
'b' | [('a', 2), ('b', 2)] | Increment count of 'b' |
'b' | [('a', 2)] | Increment count of 'b' and remove 'b' as count==k |
'a' | [] | Increment count of 'a' and remove 'a' as count==k |
'c' | [('c', 1)] | Push 'c' |
'c' | [('c', 2)] | Increment count of 'c' |
And the final string obtained by concatenating characters based on their count in the stack is 'cc'
.
Solution Implementation
1class Solution:
2 def removeDuplicates(self, s: str, k: int) -> str:
3 # Initialize an empty list to use as a stack.
4 character_stack = []
5
6 # Iterate over each character in the input string.
7 for character in s:
8 # If the stack is not empty and the top element of the stack has the same character,
9 # increase the count of that character in the stack.
10 if character_stack and character_stack[-1][0] == character:
11 character_stack[-1][1] += 1
12 # If the count reaches k, remove (pop) it from the stack.
13 if character_stack[-1][1] == k:
14 character_stack.pop()
15 else:
16 # If the character is not at the top of the stack (or if the stack is empty), add it with a count of 1.
17 character_stack.append([character, 1])
18
19 # Reconstruct the string without duplicates by multiplying the character by its count.
20 # This joins all the tuples in the stack, which holds the count of each character (not removed).
21 result = ''.join(character * count for character, count in character_stack)
22 return result
23
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4class Solution {
5 public String removeDuplicates(String s, int k) {
6 // Initialize a stack to keep track of characters and their counts.
7 Deque<int[]> stack = new ArrayDeque<>();
8
9 // Loop through each character of the string.
10 for (int i = 0; i < s.length(); ++i) {
11 // Convert the character to an index (0 for 'a', 1 for 'b', etc.).
12 int index = s.charAt(i) - 'a';
13
14 // If stack is not empty and the character on the top of the stack is the same as the current one,
15 // increase the count, otherwise push a new pair to the stack.
16 if (!stack.isEmpty() && stack.peek()[0] == index) {
17 // Increment the count and use modulo operation to reset to 0 if it hits the `k`.
18 stack.peek()[1] = (stack.peek()[1] + 1) % k;
19
20 // If the count becomes 0 after reaching k, pop the element from the stack.
21 if (stack.peek()[1] == 0) {
22 stack.pop();
23 }
24 } else {
25 // If stack is empty or the top element is different, push the new character and count (1).
26 stack.push(new int[] {index, 1});
27 }
28 }
29
30 // Initialize a StringBuilder to collect the result.
31 StringBuilder result = new StringBuilder();
32
33 // Build the result string by iterating over the stack in LIFO order.
34 for (var element : stack) {
35 // Retrieve the character from the integer index.
36 char c = (char) (element[0] + 'a');
37 // Append the character element[1] (count) times.
38 for (int i = 0; i < element[1]; ++i) {
39 result.append(c);
40 }
41 }
42
43 // The characters were added in reverse order, so reverse the whole string to get the correct order.
44 result.reverse();
45
46 // Return the resultant string.
47 return result.toString();
48 }
49}
50
1class Solution {
2public:
3 // Function to remove duplicates from a string where a sequence of
4 // 'k' consecutive duplicate characters should be removed.
5 string removeDuplicates(string s, int k) {
6 // A stack to keep track of characters and their counts
7 vector<pair<char, int>> charStack;
8
9 // Traverse the given string
10 for (char& currentChar : s) {
11 // Check if the stack is not empty and the top element character is same as the current character
12 if (!charStack.empty() && charStack.back().first == currentChar) {
13 // Increase the count of the current character at the top of the stack and take modulo 'k'
14 charStack.back().second = (charStack.back().second + 1) % k;
15
16 // If the count becomes 0, it means 'k' consecutive characters are accumulated; pop them
17 if (charStack.back().second == 0) {
18 charStack.pop_back();
19 }
20 } else {
21 // Otherwise, push the current character with count 1 onto the stack
22 charStack.push_back({currentChar, 1});
23 }
24 }
25
26 // Prepare the result string
27 string result;
28
29 // Build the string by repeating each character in the stack by its count
30 for (auto& [character, count] : charStack) {
31 result += string(count, character);
32 }
33
34 // Return the final result string
35 return result;
36 }
37};
38
1// Function to remove duplicates from a string where a sequence of
2// 'k' consecutive duplicate characters should be removed.
3function removeDuplicates(s: string, k: number): string {
4 // A stack to keep track of characters and their counts
5 let charStack: Array<{ character: string; count: number }> = [];
6
7 // Traverse the given string
8 for (let currentChar of s) {
9 // Check if the stack is not empty and the top element character
10 // is the same as the current character
11 if (charStack.length > 0 && charStack[charStack.length - 1].character === currentChar) {
12 // Increase the count of the current character at the top of the stack by 1
13 charStack[charStack.length - 1].count++;
14
15 // If the count reaches 'k', it means 'k' consecutive characters are accumulated; pop them
16 if (charStack[charStack.length - 1].count === k) {
17 charStack.pop();
18 }
19 } else {
20 // Otherwise, push the current character with count 1 onto the stack
21 charStack.push({ character: currentChar, count: 1 });
22 }
23 }
24
25 // Prepare the result string
26 let result: string = '';
27
28 // Build the string by repeating each character in the stack by its count
29 for (let { character, count } of charStack) {
30 result += character.repeat(count);
31 }
32
33 // Return the final result string
34 return result;
35}
36
Time and Space Complexity
Time Complexity
The time complexity of the code can be analyzed by looking at the operations within the main loop that iterates over each character in the input string s
. Here's the breakdown:
- For each character
c
ins
, the code performs a constant-time check to see if the stackstk
is not empty and if the top element's character matchesc
. - If there's a match, it updates the count of that character on the stack, which is also a constant-time operation.
- If the count equals
k
, it pops the element from the stack. Popping from the stack takes amortized constant time. - If there is no match or the stack is empty, it pushes the current character with count 1 onto the stack. This is a constant-time operation.
Since each character in the string is processed once and each operation is constant time or amortized constant time, the overall time complexity is O(n)
, where n
is the length of string s
.
Space Complexity
The space complexity of the code is determined by the additional space used by the stack stk
:
- In the worst case, if there are no k consecutive characters that are the same, the stack will contain all distinct characters of
s
, which would takeO(n)
space. - In the best case, if all characters are removed as duplicates, the stack will be empty, so no extra space is used beyond the input string.
Thus, the space complexity of the algorithm is O(n)
, where n
is the length of string s
, representing the maximum stack size that may be needed in the worst case.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.