{x}
blog image

Remove All Adjacent Duplicates in String II

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.

 

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.

Solution Explanation for Remove All Adjacent Duplicates in String II

This problem requires removing consecutive duplicate characters from a string if their count reaches a given value k. The optimal approach uses a stack to efficiently track characters and their counts.

Approach: Using a Stack

  1. Data Structure: We employ a stack to store pairs of (character, count). The stack's top element represents the most recently encountered character and its current count.

  2. Iteration: The algorithm iterates through the input string s.

  3. Stack Operations:

    • Character Match: If the current character c matches the top of the stack's character, we increment its count. If the count reaches k, we remove the top element (the consecutive duplicates are eliminated).
    • New Character: If the current character doesn't match the top of the stack, we push a new (c, 1) pair onto the stack.

  4. Result Construction: After processing the entire string, the remaining elements in the stack represent the characters that weren't eliminated. We concatenate these characters to form the final string.

Code Implementation (Python)

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # Stack to store (character, count) pairs
 
        for char in s:
            if not stack or stack[-1][0] != char:  # New character
                stack.append([char, 1])
            else:  # Existing character
                stack[-1][1] += 1
                if stack[-1][1] == k:  # Remove duplicates if count reaches k
                    stack.pop()
 
        result = ""
        for char, count in stack:
            result += char * count
 
        return result

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once. Stack operations (push and pop) take constant time.

  • Space Complexity: O(n) in the worst case. The stack could potentially store all characters if no duplicates are removed. In the best case (all characters are removed), the space complexity is O(1).

Code Implementation in other languages (briefly):

The logic remains the same across different languages. The primary difference lies in the syntax and data structures used.

Java: Uses Deque<int[]> (or a similar stack implementation) to store (character index, count).

C++: Uses vector<pair<char, int>> as the stack.

Go: Uses a slice of structs to represent the stack. This requires defining a custom struct for (character, count) pairs.

The core algorithm remains consistent across all implementations, ensuring efficient removal of consecutive duplicates.