Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 1209. Remove All Adjacent Duplicates in String II

Given a string s and integer k, repeatedly remove any run of k equal adjacent characters until no more removals are possible and return the final string. The core challenge is to handle cascading deletions efficiently by tracking consecutive character counts (often via a stack of character-count pairs) rather than rescanning the string.

Asked at:

Apple

DESCRIPTION

Input:

s = "deeedbbcccbdaa", k = 3

Output:

"aa"

Explanation: First remove "eee" → "deedbbcccbdaa". Then remove "ccc" → "deedbbdaa". Then remove "ddd" (merged) → "aa". No more removals possible.

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s contains only lowercase English letters

Understanding the Problem

Let's understand what we're being asked to do. Given a string like s = "deeedbbcccbdaa" and k = 3, we need to repeatedly remove any run of 3 or more consecutive equal characters.

Tracing through: We see "eee" (3 consecutive e's) - remove them! Now we have "deedbbcccbdaa". Wait, now "ccc" appears (3 consecutive c's) - remove them too! This gives "deedbbdaa". Now "ddd" appears (the two d's merged!) - remove them! Final result: "aa".

Key insight: Removals can cascade. After removing one group, adjacent characters might merge to form a new group that also needs removal!

Important constraint: We must handle these cascading deletions efficiently. Rescanning the entire string after each removal would be too slow.

Edge cases to consider: What if the entire string gets deleted? (return empty string ""). What if no removals are possible? (return original string). What if k = 1? (everything gets deleted).

Brute Force Approach

The straightforward approach is to repeatedly scan the string looking for runs of k consecutive equal characters. When found, remove that run and start scanning from the beginning again. Continue this process until a complete scan finds no removals. This approach is simple to understand but inefficient because each removal requires rebuilding the string and rescanning from the start, potentially checking the same characters many times.

Visualization

def remove_k_adjacent(s, k):
    """
    Repeatedly remove runs of k equal adjacent characters.
    Brute force: scan entire string, find first run of k, remove it, rescan from start.
    """
    # Keep removing until no more runs of k found
    while True:
        # Scan through string to find first run of k equal characters
        found = False
        i = 0
        
        while i < len(s):
            # Count consecutive equal characters starting at position i
            j = i
            while j < len(s) and s[j] == s[i]:
                j += 1
            
            run_length = j - i
            
            # If we found a run of exactly k characters, remove it
            if run_length == k:
                # Remove the run by slicing string
                s = s[:i] + s[j:]
                found = True
                break
            
            # Move to next different character
            i = j
        
        # If no run found in complete scan, we're done
        if not found:
            break
    
    return s

Start brute force removal of k adjacent duplicates

0 / 108

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^2 / k) In the worst case, we might need O(n/k) removal passes, and each pass scans O(n) characters, giving O(n^2/k) time. For example, with k=2 and string "aabbccdd...", each pass removes one pair and we need n/2 passes.

Space Complexity: O(n) We need O(n) space to store the string as we rebuild it after each removal

Building Intuition

When we remove a group of characters, the characters before and after that group become adjacent. If they're the same character, they might now form a group large enough to remove!

This means we need to track consecutive character counts as we scan through the string, and when a removal happens, we need to remember what came before to check for merging.

If we naively rescan the string after each removal, we'd have O(n²) time complexity in the worst case (imagine removing one character at a time from the end).

But if we track counts as we go and remember previous characters, we can handle all cascading deletions in a single pass through the string - O(n) time!

Imagine building a tower of blocks, where each block has a letter and a count:

As you add blocks, if the top block has the same letter as the new block, you increase its count. If the count reaches k, you remove that block entirely.

Now the block underneath becomes the new top - if it matches the next incoming block, they might merge and trigger another removal! This 'last-in, first-out' pattern with counts naturally handles cascading deletions.

Common Mistakes

Forgetting to handle cascading deletions - removing one group might create a new group that also needs removal, which the naive approach misses without rescanning

Not tracking counts correctly - when characters merge after a removal, you must add their counts together, not reset to 1

Reconstructing the result string incorrectly - the stack stores characters in order, but you need to repeat each character according to its count (e.g., ('a', 2) becomes "aa")

Off-by-one errors with k - make sure to remove when count equals k, not when it exceeds k, and handle the case where count might temporarily exceed k before removal

Not handling empty result - if all characters are removed, return an empty string, not null or an error

Optimal Solution

The optimal approach uses a stack to track character-count pairs as we scan through the string. For each character, if the stack's top has the same character, increment its count; otherwise, push a new pair. When any count reaches k, pop that pair from the stack (removal). This naturally handles cascading deletions because after popping, the previous character becomes the new top and can merge with subsequent characters. Finally, reconstruct the result string from the stack.

Visualization

def remove_k_adjacent_duplicates(s, k):
    """
    Remove runs of k equal adjacent characters using a stack.
    Stack stores (character, count) pairs.
    """
    # Initialize stack to track character-count pairs
    stack = []
    
    # Process each character in the string
    for char in s:
        # If stack is not empty and top character matches current
        if stack and stack[-1][0] == char:
            # Increment count of the top character
            stack[-1] = (char, stack[-1][1] + 1)
            
            # If count reaches k, remove this run
            if stack[-1][1] == k:
                stack.pop()
        else:
            # Push new character with count 1
            stack.append((char, 1))
    
    # Reconstruct result string from stack
    result = []
    for char, count in stack:
        result.append(char * count)
    
    return ''.join(result)

Start: Remove all adjacent duplicates of length k

0 / 61

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We scan through the string once, and each character is pushed and popped from the stack at most once, resulting in linear time complexity

Space Complexity: O(n) The stack stores at most n character-count pairs in the worst case (when no removals occur), requiring O(n) space

What We've Learned

Stack with count aggregation: Use a stack storing (character, count) pairs instead of individual characters when you need to track consecutive occurrences - this allows O(1) count updates and eliminates the need to rescan for duplicates after each deletion.
Cascading deletion handling: When a removal creates new adjacent duplicates (e.g., "deeedbbcccbdaa" with k=3), a stack naturally handles cascading deletions by checking the top element after each push - the LIFO property ensures newly adjacent characters are immediately evaluated.
Single-pass with lookahead avoidance: Instead of scanning ahead to count duplicates or rescanning after deletions, increment the count of the stack's top element when the current character matches - this achieves O(n) time by processing each character exactly once.
Stack-to-string reconstruction: When building the final result from a stack of (char, count) pairs, iterate from bottom to top and repeat each character by its count - forgetting to expand counts or iterating in wrong order are common mistakes that produce incorrect output.
Threshold-based removal pattern: This stack approach extends to any problem requiring removal when a threshold is met (k consecutive elements, sum exceeds limit, pattern matches) - the key is storing aggregate metadata alongside elements rather than raw values.
Space-time tradeoff insight: While the stack uses O(n) space in worst case (all unique characters), it eliminates the O(n²) time of naive string manipulation approaches that repeatedly scan and rebuild strings, making it essential for large inputs where k is small relative to n.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid November, 2025

Salesforce

Mid-level

Late October, 2025

Apple

Senior

Late September, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1209. Remove All Adjacent Duplicates in String II

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact