Leetcode 1209. Remove All Adjacent Duplicates in String II

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).

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.

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

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.

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.

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)

• 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.