We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove All Adjacent Duplicates in String II

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem involves removing groups of adjacent characters that occur k times or more.
  • A stack can be effectively used to keep track of characters and their counts, allowing for easy removal when the count reaches k.
  • We need to iterate through the string while maintaining the order of characters that do not form a group of k.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Each character is processed at most twice. Space Complexity: O(n), in the worst case, for the stack used to store the characters and their counts.

Solution

We will use a stack to keep track of characters and their consecutive counts. As we iterate through the characters of the string, we will:

  1. Push characters onto the stack alongside their counts.
  2. If the count of a character reaches k, we will pop it off the stack.
  3. At the end of the iteration, we will rebuild the string from the stack.

This approach efficiently handles the duplicate removal while ensuring we only traverse the string a limited number of times.

Code Solutions

def removeDuplicates(s: str, k: int) -> str:
    stack = []  # Stack to keep track of characters and their counts
    for char in s:
        if stack and stack[-1][0] == char:
            # If the top of the stack is the same character, increment the count
            stack[-1][1] += 1
        else:
            # Otherwise, push the new character onto the stack
            stack.append([char, 1])
        
        # If the count reaches k, remove it from the stack
        if stack[-1][1] == k:
            stack.pop()
    
    # Rebuild the final string
    result = ''.join(char * count for char, count in stack)
    return result
← Back to All Questions