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.

Examples

Example 1:

1
2
3
4
5

Input:
s = "abcd", k = 2
Output:
 "abcd"
Explanation: There's nothing to delete.

Example 2:

1
2
3
4
5
6
7
8

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:

1
2
3
4

Input:
s = "pbbcggttciiippooaais", k = 2
Output:
 "ps"

Similar Problem

Remove All Adjacent Duplicates In String 1

Solution

Method 1 – Stack for Character and Count Tracking

Intuition

The key idea is to use a stack to keep track of characters and their consecutive counts. As we iterate through the string, we push each character and its count onto the stack. If the count reaches k, we remove that group from the stack, effectively removing k adjacent duplicates. This process continues until the end of the string, ensuring all k-adjacent duplicates are removed.

Approach

  1. Initialize an empty stack to store pairs of (character, count).
  2. Iterate through each character in the string:
    • If the stack is not empty and the top character matches the current character, increment the count.
    • Otherwise, push (character, 1) onto the stack.
    • If the count at the top of the stack reaches k, pop it from the stack.
  3. After processing, reconstruct the string by repeating each character in the stack by its count.

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, as each character is pushed and popped at most once.
  • 🧺 Space complexity: O(n), for the stack used to store character and count pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<Pair<Character, Integer>> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peekLast().getKey() == c) {
                int cnt = stack.peekLast().getValue() + 1;
                stack.pollLast();
                stack.offerLast(new Pair<>(c, cnt));
                if (cnt == k) stack.pollLast();
            } else {
                stack.offerLast(new Pair<>(c, 1));
            }
        }
        StringBuilder ans = new StringBuilder();
        for (Pair<Character, Integer> p : stack) {
            for (int i = 0; i < p.getValue(); i++) ans.append(p.getKey());
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<pair<char, int>> st;
        for (char c : s) {
            if (!st.empty() && st.top().first == c) {
                int cnt = st.top().second + 1;
                st.pop();
                st.push({c, cnt});
                if (cnt == k) st.pop();
            } else {
                st.push({c, 1});
            }
        }
        string ans;
        vector<pair<char, int>> temp;
        while (!st.empty()) {
            temp.push_back(st.top());
            st.pop();
        }
        reverse(temp.begin(), temp.end());
        for (auto& p : temp) ans.append(p.second, p.first);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack: list[tuple[str, int]] = []
        for c in s:
            if stack and stack[-1][0] == c:
                cnt = stack[-1][1] + 1
                stack.pop()
                stack.append((c, cnt))
                if cnt == k:
                    stack.pop()
            else:
                stack.append((c, 1))
        ans = []
        for ch, cnt in stack:
            ans.append(ch * cnt)
        return ''.join(ans)