Clear Digits

Difficulty: Easy | Acceptance: 82.70% | Paid: No Topics: String, Stack, Simulation

You are given a string s.

You repeatedly perform the following operation on s:

1. Find the leftmost digit in s.
2. If there is a non-digit character immediately to the left of this digit, delete both the digit and the non-digit character.

Return the resulting string after all operations are performed.

• Examples
• Constraints
• Stack Simulation
• Two Pointers

Examples

Example 1:

Input: s = "abc"
Output: "abc"
Explanation:
There is no digit in the string.

Example 2:

Input: s = "cb34"
Output: ""
Explanation:
First operation: Remove '3' and 'b' -> "c4".
Second operation: Remove '4' and 'c' -> "".

Constraints

1 <= s.length <= 100
s consists only of lowercase English letters and digits.

Stack Simulation

Intuition The problem requires removing a digit and the character immediately to its left. This “last in, first out” behavior (where the most recent non-digit character is removed by a new digit) maps perfectly to a stack data structure.

Steps

• Initialize an empty stack.
• Iterate through each character in the string s.
• If the character is a digit, pop the top element from the stack (removing the non-digit to the left).
• If the character is not a digit, push it onto the stack.
• After processing all characters, join the elements remaining in the stack to form the result string.

class Solution:
    def clearDigits(self, s: str) -> str:
        stack = []
        for char in s:
            if char.isdigit():
                if stack:
                    stack.pop()
            else:
                stack.append(char)
        return "".join(stack)

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(n), to store the stack. In the worst case (no digits), the stack stores all characters.
• Notes: Using a StringBuilder (Java) or string (C++) as a stack is more efficient than a generic Stack class.

Two Pointers

Intuition We can simulate the stack behavior in-place using two pointers to avoid the extra space overhead of a separate stack structure. One pointer acts as the “write” head (top of the stack), and the other iterates through the input.

Steps

• Convert the string to a character array (if necessary for the language).
• Initialize a pointer write to 0.
• Iterate through the string with a pointer read.
• If s[read] is a digit, decrement write (effectively popping the last valid character).
• If s[read] is not a digit, assign s[write] = s[read] and increment write.
• The result consists of characters from index 0 to write - 1.

class Solution:
    def clearDigits(self, s: str) -> str:
        res = list(s)
        write = 0
        for read in range(len(s)):
            if s[read].isdigit():
                if write > 0:
                    write -= 1
            else:
                res[write] = s[read]
                write += 1
        return "".join(res[:write])

Complexity

• Time: O(n), where n is the length of the string. We pass through the string once.
• Space: O(1) auxiliary space (excluding the input array storage), as we modify the array in-place.
• Notes: This is the most space-efficient approach for mutable string types.