#1209

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove All Adjacent Duplicates in String II

Remove all adjacent duplicates in the string using stack-based state management with a given threshold k.

Problem Statement

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 right side of the deleted substring to concatenate together.

Repeat the process of removing k adjacent duplicates until no more can be removed. Return the final string after all removals. It is guaranteed that the answer is unique.

Examples

Example 1

Input: s = "abcd", k = 2

Output: "abcd"

There's nothing to delete.

Example 2

Input: s = "deeedbbcccbdaa", k = 3

Output: "aa"

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"

Example details omitted.

Constraints

1 <= s.length <= 105
2 <= k <= 104
s only contains lowercase English letters.

Solution Approach

Stack-based Approach

Use a stack to store characters, and for each character, track its count. If the count reaches k, remove those characters from the stack and continue processing the string.

Iterate Through String

Process the string character by character, pushing each character onto the stack. For consecutive duplicates, increment the count. When the count reaches k, pop the characters from the stack.

Efficient String Construction

After processing the stack, reconstruct the string from the stack by concatenating the remaining characters. This avoids unnecessary string concatenations during the removal process.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach, but typically, it is O(n), where n is the length of the string. Space complexity depends on the stack's usage, but in the worst case, it is O(n).

What Interviewers Usually Probe

Ability to manage stack operations effectively under constraints.
Handling edge cases such as no adjacent duplicates or very large inputs.
Efficient handling of string processing using stack-based state management.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly manage the stack during consecutive removals, leading to incorrect outputs.
Not correctly handling cases where no characters can be removed, resulting in inefficient operations.
Overcomplicating the problem by using unnecessary additional data structures.

Follow-up variants

Increase the value of k to test scalability.
Modify the input to include no adjacent duplicates and check if the solution performs optimally.
Test with large inputs to evaluate the time and space complexity of the solution.

FAQ

What is the core approach to solving the Remove All Adjacent Duplicates in String II problem?

The key approach involves using a stack to track characters and their counts. When the count reaches k, you remove the characters from the stack.

How do stacks help in solving the Remove All Adjacent Duplicates in String II problem?

Stacks manage character sequences efficiently by pushing characters and popping them when k adjacent duplicates are found, which simplifies the removal process.

What are the time and space complexities for the Remove All Adjacent Duplicates in String II problem?

Typically, the time complexity is O(n), and space complexity is O(n) due to the stack-based solution.

How do edge cases affect the solution for Remove All Adjacent Duplicates in String II?

Edge cases like no duplicates or large values of k can affect performance. Efficient stack management ensures optimal handling in these cases.

What can be done to optimize the solution for the Remove All Adjacent Duplicates in String II problem?

Optimizing the solution involves ensuring that the stack only holds necessary characters and avoiding repeated string concatenations during the process.

terminal

Solution

Solution 1: Stack

We can traverse the string $s$, maintaining a stack that stores the characters and their occurrence counts. When traversing to character $c$, if the character at the top of the stack is the same as $c$, we increment the count of the top element by one; otherwise, we push the character $c$ and count $1$ into the stack. When the count of the top element equals $k$, we pop the top element from the stack.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            if stk and stk[-1][0] == c:
                stk[-1][1] = (stk[-1][1] + 1) % k
                if stk[-1][1] == 0:
                    stk.pop()
            else:
                stk.append([c, 1])
        ans = [c * v for c, v in stk]
        return "".join(ans)

Continue Practicing

#1190 reverse substrings between each pair of parentheses #1249 minimum remove to make valid parentheses #1111 maximum nesting depth of two valid parentheses strings