Vultr DocsLatest Content

Remove All Adjacent Duplicates in String II

Updated on 24 June, 2025
Remove All Adjacent Duplicates in String II header image

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

  • C++
  • Java
cpp 
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);
}

The provided C++ function deduplicateCharacters tackles the problem of removing sequences of the same character that appear consecutively num times in a given string str. The function uses a stack to keep track of the count of consecutive characters and operates directly on the input string to achieve an in-place solution.

  • The function takes two parameters:

    • str: the string from which duplicates will be removed.
    • num: the threshold number of consecutive duplicate characters that triggers removal.

  • The process iterates over each character in the string:

    • Updates the character position in str directly to prevent gaps due to removed duplicates.
    • Utilizes a stack to manage counts of consecutive duplicated characters. New counts are pushed onto the stack when current and previous characters differ.
    • When a count reaches the specified num, indicating a complete sequence of consecutive duplicates to be removed, the stack is popped and newLength is adjusted to effectively delete this sequence from the working subset of the string.

  • Finally, the function returns the appropriately resized substring of str, which ensures all leftover characters are consecutive duplicates of less than num times.

The function highlights efficient string manipulation and stack utilization to track and adjust character sequences dynamically. This approach minimizes the need for auxiliary data structures, thereby optimizing space and time complexity.

java 
public String eliminateRepeatedChars(String inputStr, int threshold) {
    Stack<Integer> charCounts = new Stack<>();
    char[] resultArr = inputStr.toCharArray();
    int idxRes = 0;
    for (int i = 0; i < inputStr.length(); i++, idxRes++) {
        resultArr[idxRes] = resultArr[i];
        if (idxRes == 0 || resultArr[idxRes] != resultArr[idxRes - 1]) {
            charCounts.push(1);
        } else {
            int counter = charCounts.pop() + 1;
            if (counter == threshold) {
                idxRes -= threshold;
            } else {
                charCounts.push(counter);
            }
        }
    }
    return new String(resultArr, 0, idxRes);
}

You have a Java function named eliminateRepeatedChars designed to remove adjacent duplicate characters in a string based on a given threshold. The function handles the process of removing excessive duplicates using stack-based operations and character array manipulations. Below are the systematic operations of the function to achieve the desired result:

  1. Initialize a Stack<Integer> named charCounts to track the occurrences of each character.
  2. Convert inputStr to a character array resultArr to facilitate direct manipulation.
  3. Set up a for-loop to iterate over each character in inputStr. The loop also incrementally extends an index idxRes, which tracks the position in the result array.
  4. Within the loop, compare each character to the one before it to identify consecutive duplicates.
  5. If a new character type is encountered (or at the start of the array), push 1 onto charCounts.
  6. If a duplicate is found, pop the count from the stack, increment it, and check against the threshold.
  7. If the incremented count equals threshold, retreat idxRes to effectively remove the string of duplicates. If not, push the incremented count back onto the stack.
  8. After the loop, reconstruct the string using the elements from resultArr up to idxRes to ensure removed characters are not included.
  9. The function returns a new string showing the result after duplicates above the threshold have been removed.

By implementing these steps, the function meticulously ensures that all adjacent duplicates of characters that meet or exceed the threshold are eliminated from the input string, ensuring concise and efficient string manipulation.

Comments

No comments yet.