1209. Remove All Adjacent Duplicates in String II

MediumStackString
Leetcode Link

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:

  1. Iterate over each character in the input string.
  2. 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.
  3. If the count of the top element becomes equal to k after incrementing, it means we have found k adjacent identical characters, and we can remove them from the stack (mimicking the removal from the string).
  4. If the stack's top element is not c, or if the stack is empty, we push the new character c onto the stack with an initial count of one, as it starts a new potential group.
  5. 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.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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:

  1. 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.

  2. 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 reached k. If the count is k, this signifies a k 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 with c and the count 1.

  3. Reconstructing the String: After the iteration, the stack contains characters that did not qualify for k duplicate removal, with their counts being less than k. Now, to reconstruct the final string, we multiply (*) each character c by its count v 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 to 0 if it reaches k (since k % k is 0).
  • if stk[-1][1] == 0: stk.pop(): If after incrementing, the count becomes 0, meaning we have k duplicates, we remove (pop) the top element from the stack.
  • else: stk.append([c, 1]): In case the character c is different or the stack is empty, we append c along with the initial count 1 as a new group in the stack.
  • ans = [c * v for c, v in stk]: We build the answer list by multiplying the character c by its count v.
  • return "".join(ans): Join all strings in the ans 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example 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:

  1. Initializing the Stack: We start with an empty stack stk.

  2. 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 count 1. Increment count: ['b', 2].
    • Another 'b' comes. Increment count: ['b', 3]. But now we've hit k duplicates, so we remove this from the stack.
    • The next character is 'a'. Top of the stack is 'a' with count 2. Increment the count and now we have 'a' with count 3, 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 count 1. 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 the k duplicate threshold.

  3. 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'.

Hence, the final string after performing k duplicate removals is "cc".

Here is the resultant stack operations visualized at each step:

InputStackOperation
'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
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

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 in s, the code performs a constant-time check to see if the stack stk is not empty and if the top element's character matches c.
  • 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 take O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Stack Intro

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫