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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove All Adjacent Duplicates in String II

Number: 1320

Difficulty: Medium

Paid? No

Companies: Bloomberg, Grammarly, Meta, Amazon, Oracle, Goldman Sachs, Walmart Labs, TikTok, Google, Microsoft, ZScaler, Disney, FactSet

Problem Description

We 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 right parts to merge. We repeatedly perform these removals until no more can be done, and then we return the final string.

Key Insights

  • Use a stack to track characters along with their consecutive counts.
  • As you iterate through the string, if the current character is the same as the one on top of the stack, increment its count.
  • When a character's count equals k, remove it from the stack.
  • Finally, reconstruct the string from the stack content.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we process each character once.
Space Complexity: O(n) in the worst case where no removals occur and all characters are stored in the stack.

Solution

We utilize a stack to store pairs of (character, count). For every character encountered, we check if it matches the top element on the stack:

  • If it does, we increase its count.
  • If the count reaches k, we remove that element from the stack.
  • Otherwise, if it differs, we push a new pair. After processing all characters, the stack is rebuilt into the final string by repeating each character by its recorded count.

Code Solutions

# Function to remove all adjacent duplicates with a count of k
def removeDuplicates(s: str, k: int) -> str:
    # Stack to store pairs [character, count]
    stack = []
    for char in s:
        # If there is at least one element and the last character matches current char
        if stack and stack[-1][0] == char:
            stack[-1][1] += 1  # Increment its count
            # If count equals k, remove the element from the stack
            if stack[-1][1] == k:
                stack.pop()
        else:
            # Push new character with count 1
            stack.append([char, 1])
    # Reconstruct final string from the stack
    result = []
    for char, count in stack:
        result.append(char * count)
    return "".join(result)

# Example usage:
print(removeDuplicates("deeedbbcccbdaa", 3))  # Expected Output: "aa"
← Back to All Questions