LeetCode 3174 - Clear Digits

In this problem, we are given a string s that contains lowercase English letters and digits. The task is to repeatedly remove digits according to a very specific rule. Whenever we encounter a digit, we must delete two characters: 1. The digit itself 2.

leetcodeeasystringstacksimulation

LeetCode Problem 3174

Difficulty: 🟢 Easy
Topics: String, Stack, Simulation

Solution

Problem Understanding

In this problem, we are given a string s that contains lowercase English letters and digits. The task is to repeatedly remove digits according to a very specific rule.

Whenever we encounter a digit, we must delete two characters:

  1. The digit itself
  2. The closest non-digit character to its left

This process continues until all digits are removed.

The important detail is that the removal always pairs a digit with the nearest letter before it. Because the input guarantees that all digits can eventually be removed, we never need to handle invalid situations where a digit has no available letter on its left.

For example, consider the string "ab3c2":

  • The digit '3' removes itself and the closest letter to its left, which is 'b'
  • The string effectively becomes "ac2"
  • Then '2' removes itself and 'c'
  • Final result is "a"

The output should contain only the letters that survive all removal operations.

The constraints are very small:

  • 1 <= s.length <= 100
  • The string contains only lowercase letters and digits

Because the input size is tiny, even less efficient solutions could pass. However, the goal is to design a clean and optimal approach.

There are several important edge cases to think about:

  • Strings with no digits, such as "abc"
  • Strings where every letter gets removed, such as "cb34"
  • Digits appearing consecutively
  • Digits appearing near the beginning of the string
  • Alternating letters and digits like "a1b2c3"

The problem guarantee that every digit can be removed safely simplifies the implementation because we never need to check for invalid operations.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly scan the string until no digits remain.

Whenever we find a digit:

  1. Search leftward to find the closest non-digit character
  2. Remove both characters
  3. Rebuild the string
  4. Restart scanning

This approach works because it directly simulates the problem statement exactly as described.

However, repeated string rebuilding is inefficient. Strings are immutable in many languages, including Python, so every deletion creates a new string. If we repeatedly scan and rebuild the string, the overall complexity can become quadratic.

Even though the constraints are small enough for this to pass, it is not the cleanest or most efficient solution.

Optimal Approach

The key observation is that every digit removes the most recent unmatched letter to its left.

This behavior is exactly what a stack is designed for.

As we scan the string from left to right:

  • If we see a letter, we push it onto the stack
  • If we see a digit, we remove the most recent letter by popping from the stack

At the end, the stack contains exactly the surviving characters.

This works because the closest non-digit character to the left is always the most recently added unmatched letter.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly scans and rebuilds the string
Optimal O(n) O(n) Uses a stack to process characters in one pass

Algorithm Walkthrough

  1. Initialize an empty stack.

The stack will store letters that have not yet been removed by digits. 2. Traverse the string from left to right.

We process characters in order because each digit only affects characters that appear before it. 3. If the current character is a letter, push it onto the stack.

This means the character is currently available to be removed by a future digit. 4. If the current character is a digit, pop one character from the stack.

The top of the stack represents the closest non-digit character to the left. 5. Continue until all characters have been processed. 6. Join the remaining characters in the stack into a final string.

These are the letters that were never removed.

Why it works

The stack always maintains the set of unmatched letters in their original order. Whenever a digit appears, the problem requires removing the closest letter to its left. Since the most recent unmatched letter is exactly the top of the stack, popping from the stack performs the correct operation. By processing characters from left to right, every digit removes the proper character, guaranteeing correctness.

Python Solution

class Solution:
    def clearDigits(self, s: str) -> str:
        stack: list[str] = []

        for char in s:
            if char.isdigit():
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

The implementation uses a list as a stack.

We iterate through every character in the string exactly once.

If the character is a digit, we remove the most recent unmatched letter using pop(). The problem guarantees this operation is always valid.

If the character is a letter, we append it to the stack because it may later be removed by a digit.

Finally, we join the remaining characters together to form the answer.

This implementation directly mirrors the stack-based algorithm described earlier.

Go Solution

func clearDigits(s string) string {
    stack := make([]rune, 0)

    for _, char := range s {
        if char >= '0' && char <= '9' {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, char)
        }
    }

    return string(stack)
}

The Go implementation uses a slice of rune values as the stack.

Instead of using a built in stack structure, Go commonly uses slices for stack operations:

  • append() pushes elements
  • stack[:len(stack)-1] pops elements

Using rune instead of byte is a safer general practice for string processing, although this specific problem only contains ASCII characters.

Unlike Python, Go does not have a built in isdigit() method, so we manually check whether the character falls between '0' and '9'.

Worked Examples

Example 1

Input:

s = "abc"

Processing steps:

Character Action Stack
'a' Push letter ['a']
'b' Push letter ['a', 'b']
'c' Push letter ['a', 'b', 'c']

Final result:

"abc"

No digits appear, so no removals happen.

Example 2

Input:

s = "cb34"

Processing steps:

Character Action Stack
'c' Push letter ['c']
'b' Push letter ['c', 'b']
'3' Pop closest left letter ['c']
'4' Pop closest left letter []

Final result:

""

The first digit removes 'b', and the second digit removes 'c'.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(n) The stack may store all letters

The algorithm is linear because every character is visited exactly once. Stack operations such as append and pop are constant time.

In the worst case, the stack stores every character, such as when the string contains no digits, so the space complexity is linear as well.

Test Cases

solution = Solution()

assert solution.clearDigits("abc") == "abc"          # no digits
assert solution.clearDigits("cb34") == ""            # all letters removed
assert solution.clearDigits("a1") == ""              # single removal
assert solution.clearDigits("ab12") == ""            # consecutive digits
assert solution.clearDigits("abc123") == ""          # all letters removed in order
assert solution.clearDigits("a1b2c3") == ""          # alternating letters and digits
assert solution.clearDigits("abcd1") == "abc"        # remove last letter
assert solution.clearDigits("x2y3") == ""            # repeated removals
assert solution.clearDigits("leetcode") == "leetcode" # letters only
assert solution.clearDigits("z1x2c3v4") == ""        # chain removals
assert solution.clearDigits("ab3c2d") == "ad"        # mixed removals

Test Summary

Test Why
"abc" Validates behavior with no digits
"cb34" Validates complete removal
"a1" Smallest valid removal case
"ab12" Tests consecutive digits
"abc123" Ensures repeated stack pops work
"a1b2c3" Tests alternating pattern
"abcd1" Removes only the nearest left letter
"x2y3" Verifies repeated removals
"leetcode" Confirms unchanged output for letters only
"z1x2c3v4" Stress test for repeated popping
"ab3c2d" Mixed remaining and removed characters

Edge Cases

One important edge case is a string with no digits, such as "abc". A naive implementation might unnecessarily attempt removals or fail to return the original string correctly. In the stack solution, every character is simply pushed onto the stack, and the final joined result matches the input exactly.

Another important case is consecutive digits, such as "ab12". Some implementations may incorrectly attempt to remove already deleted characters. The stack naturally handles this because each digit pops only the most recent remaining letter.

A third important edge case is when every character gets removed, such as "cb34". Some implementations may accidentally return None or leave leftover characters due to indexing mistakes. The stack solution correctly ends with an empty stack, and joining an empty list produces an empty string.

A final subtle case is alternating letters and digits like "a1b2c3". This pattern continuously pushes and pops elements. The stack structure handles this naturally because every digit immediately removes the most recent letter.