Problem Description

You are given a string s that contains both digits (0-9) and non-digit characters.

Your task is to remove all digits from the string by repeatedly performing this specific operation:

• Find the first digit in the string
• Delete that digit along with the closest non-digit character to its left

Keep repeating this operation until all digits are removed from the string.

For example, if you have the string "abc3de2f":

• First operation: Find digit '3', remove it along with 'c' (closest non-digit to its left) → "abde2f"
• Second operation: Find digit '2', remove it along with 'e' (closest non-digit to its left) → "abdf"
• Result: "abdf"

Important constraints:

• You can only perform the operation if there is at least one non-digit character to the left of the digit
• If a digit has no non-digit character to its left, it cannot be removed using this operation

The solution uses a stack to efficiently simulate this process. When traversing the string:

• If the current character is a non-digit, push it onto the stack
• If the current character is a digit, pop the most recent non-digit from the stack (which represents the closest non-digit to the left)

After processing all characters, the remaining elements in the stack form the final string with all digits and their corresponding non-digit pairs removed.

Intuition

The key insight is recognizing that when we need to find "the closest non-digit character to the left" of a digit, we're essentially looking at the most recently encountered non-digit character before this digit appears.

This pattern immediately suggests using a stack data structure because:

• When we encounter non-digit characters, we need to store them for potential future removal
• When we encounter a digit, we need to remove the most recent non-digit character (last-in, first-out behavior)

Think of it like this: as we read the string from left to right, we're building up a collection of non-digit characters. Each time we see a digit, it "consumes" or "cancels out" the most recent non-digit character we've collected.

For example, with string "ab2c3":

• Read 'a': collect it (stack: ['a'])
• Read 'b': collect it (stack: ['a', 'b'])
• Read '2': this digit removes the closest non-digit to its left, which is 'b' (stack: ['a'])
• Read 'c': collect it (stack: ['a', 'c'])
• Read '3': this digit removes 'c' (stack: ['a'])
• Result: 'a'

The beauty of this approach is that we don't need to actually perform multiple passes or physically remove characters from the middle of the string. Instead, we can process everything in a single pass - the stack naturally maintains only the characters that survive the removal process.

This transforms what initially seems like a complex string manipulation problem requiring multiple scans and deletions into a simple one-pass algorithm with O(n) time complexity.

Learn more about Stack patterns.

Solution Approach

The solution uses a stack-based simulation to process the string in a single pass.

Here's the step-by-step implementation:

1. Initialize an empty stack stk to store non-digit characters that haven't been removed yet.

2. Traverse the string character by character:

   • For each character c in the string s:
     • If c is a digit (checked using c.isdigit()):
       • Pop the top element from the stack using stk.pop()
       • This simulates removing the closest non-digit character to the left
     • If c is not a digit:
       • Push it onto the stack using stk.append(c)
       • This character might be removed later if a digit appears to its right

3. Build the result: After processing all characters, the stack contains only the non-digit characters that survived the removal process. Join them into a string using "".join(stk).

Implementation Details:

class Solution:
    def clearDigits(self, s: str) -> str:
        stk = []
        for c in s:
            if c.isdigit():
                stk.pop()  # Remove closest non-digit to the left
            else:
                stk.append(c)  # Store non-digit for potential removal
        return "".join(stk)

Why this works:

• The stack naturally maintains the order of non-digit characters from left to right
• When we encounter a digit, the top of the stack is always the "closest non-digit character to its left"
• Characters that remain in the stack after processing are exactly those that weren't paired with any digit for removal

Time Complexity: O(n) where n is the length of the string - we process each character exactly once.

Space Complexity: O(n) for the stack in the worst case when the string contains no digits.

Example Walkthrough

Let's trace through the string "cb34" step by step to see how the stack-based solution works:

Initial state:

• String: "cb34"
• Stack: [] (empty)

Step 1: Process 'c'

• Current character: 'c' (non-digit)
• Action: Push to stack
• Stack after: ['c']

Step 2: Process 'b'

• Current character: 'b' (non-digit)
• Action: Push to stack
• Stack after: ['c', 'b']

Step 3: Process '3'

• Current character: '3' (digit)
• Action: Pop from stack (removes 'b', the closest non-digit to the left)
• Stack after: ['c']
• This simulates removing both '3' and 'b' from the original string

Step 4: Process '4'

• Current character: '4' (digit)
• Action: Pop from stack (removes 'c', the closest non-digit to the left)
• Stack after: [] (empty)
• This simulates removing both '4' and 'c' from the string

Final Result:

• Stack contents: []
• Output: "" (empty string)

The algorithm correctly identifies that:

• Digit '3' pairs with and removes 'b'
• Digit '4' pairs with and removes 'c'
• All characters are removed, resulting in an empty string

This demonstrates how the stack naturally tracks the "closest non-digit to the left" relationship - the most recently added non-digit (top of stack) is always the one that gets paired with the next digit we encounter.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once. Each operation within the loop (checking if a character is a digit, popping from the stack, or appending to the stack) takes O(1) time.

The space complexity is O(n), where n is the length of the string s. In the worst case, when the string contains no digits, all characters will be added to the stack, requiring space proportional to the length of the input string. The final string created by "".join(stk) also requires O(n) space, but this doesn't change the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Empty Stack When Popping

The most common pitfall is attempting to pop from an empty stack when encountering a digit that has no non-digit character to its left.

Problematic Code:

def clearDigits(self, s: str) -> str:
    stack = []
    for char in s:
        if char.isdigit():
            stack.pop()  # ❌ Crashes if stack is empty!
        else:
            stack.append(char)
    return "".join(stack)

What Goes Wrong:

• Input: "5abc" - The first character is a digit with no non-digit to its left
• Input: "ab12cd" - After removing 'b' for '1', the '2' tries to pop from an empty stack

Solution: Always check if the stack is non-empty before popping:

def clearDigits(self, s: str) -> str:
    stack = []
    for char in s:
        if char.isdigit():
            if stack:  # ✅ Only pop if stack has elements
                stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

2. Misunderstanding Which Character to Remove

Another pitfall is misunderstanding the problem and trying to remove the digit itself or the character to the right of the digit.

Wrong Interpretation:

def clearDigits(self, s: str) -> str:
    result = []
    for i, char in enumerate(s):
        if not char.isdigit():
            # Check if next character is a digit
            if i + 1 < len(s) and s[i + 1].isdigit():
                continue  # ❌ Skip this character
            result.append(char)
    return "".join(result)

This approach incorrectly tries to look ahead instead of using the stack to track the "closest non-digit to the left."

3. Not Preserving Order of Remaining Characters

Some might try alternative approaches that don't preserve the relative order of the remaining characters:

Incorrect Approach:

def clearDigits(self, s: str) -> str:
    # Count digits and non-digits
    digit_count = sum(1 for c in s if c.isdigit())
    non_digits = [c for c in s if not c.isdigit()]
  
    # Remove digit_count non-digits from the end
    return "".join(non_digits[:-digit_count] if digit_count else non_digits)

This incorrectly assumes we always remove from the end, when we actually need to remove the non-digit immediately preceding each digit.

Key Takeaway: The stack-based approach is elegant because it naturally handles the "closest to the left" requirement - the top of the stack is always the most recent (closest) non-digit character encountered.