Remove All Adjacent Duplicates in String II

Problem Statement

You are provided with a string s and an integer k. In this problem, you perform what's known as a k duplicate removal. This process involves identifying k consecutive, identical characters in the string and removing them completely. Once these characters are removed, the string compresses such that the characters on either side of the now-removed segment come together.

This operation is repeated iteratively until no further such k-consecutive identical characters can be found in the string. The task is to return the string after all possible k duplicate removals have been completed. You can be assured that the result returned is unique, meaning there is only one possible final state of the string after all operations have been performed.

Examples

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 <= 105
• 2 <= k <= 104
• s only contains lowercase English letters.

Approach and Intuition

The problem can be approached using a stack-based method, which effectively handles the repeated removal and concatenation process. Here's the intuitive step-by-step breakdown of the approach:

1. Initialize a stack where each element is a pair containing a character from the string and its consecutive count.
2. Traverse the characters of the string one by one:
   • For each character, increase its count if it's the same as the previous one.
   • If the count becomes equal to k, remove that character from the stack (simulating the removal of k consecutive characters).
   • If it's a different character or if a removal has just occurred, push the new character onto the stack with a count of one.
3. After processing all characters, the stack will contain only the characters that couldn't be removed in groups of k. Convert these stack elements back to a string.
4. This resultant string will be the input string transformed by repeatedly removing all possible groups of k identical consecutive characters.

By leveraging this approach, we handle the problem's constraints efficiently, minimize repetitive checks, and ensure that the operations are performed only when necessary.

Solutions

string deduplicateCharacters(string str, int num) {
    int newLength = 0;
    stack<int> charCounts;
    for (int idx = 0; idx < str.size(); ++idx, ++newLength) {
        str[newLength] = str[idx];
        if (newLength == 0 || str[newLength] != str[newLength - 1]) {
            charCounts.push(1);
        } else if (++charCounts.top() == num) {
            charCounts.pop();
            newLength -= num;
        }
    }
    return str.substr(0, newLength);
}