1209. Remove All Adjacent Duplicates in String II

2026, Oct 15 2 mins read

1. Description

Given a string s and an integer k, delete any block of k identical consecutive characters, joining the remaining parts together.
Continue deleting such blocks until none remain. Return the resulting string, which is guaranteed to be unique.

2. Example

Example 1

Input: s = “abcd”, k = 2
Output: “abcd”
Explanation: No adjacent characters form a removable pair.

Example 2

Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”
Explanation: Removing “eee” and “ccc” leaves “ddbbbdaa”. Delete “bbb” to get “dddaa”, then delete “ddd” to leave “aa”.

Example 3

Input: s = “pbbcggttciiippooaais”, k = 2
Output: “ps”
Explanation: Repeatedly deleting adjacent equal pairs leaves only “ps”.

3. Constraints

1 <= s.length <= $10^5$
2 <= k <= $10^4$
s contains only lowercase English letters.

4. Solutions

Stack with Character Counts

n = str.size()
Time complexity: O(n)
Space complexity: O(n)

 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
26
// Store consecutive character counts in a stack and pop a group when its count reaches k.
// Newly adjacent groups merge as scanning continues; rebuild the string from the remaining groups.
class Solution {
public:
    string removeDuplicates(const string &str, int k) {
        vector<pair<char, int>> letter_count;
        for (char c : str) {
            if (!letter_count.empty() && letter_count.back().first == c) {
                ++letter_count.back().second;
            } else {
                letter_count.emplace_back(c, 1);
            }

            if (letter_count.back().second == k) {
                letter_count.pop_back();
            }
        }

        string result;
        for (const auto &[letter, count] : letter_count) {
            result += string(count, letter);
        }

        return result;
    }
};

Search

Tags