# Clear Digits
**Difficulty:** EASY
[External](https://leetcode.com/problems/clear-digits)
Canonical: https://scaleengineer.com/dsa/problems/clear-digits
**Data structures:** String, Stack
**Companies:** [Flexera](https://scaleengineer.com/companies/flexera)
---
## Problem
You are given a string `s`.

Your task is to remove **all** digits by doing this operation repeatedly:

* Delete the _first_ digit and the **closest** **non-digit** character to its _left_.

Return the resulting string after removing all digits.

**Note** that the operation _cannot_ be performed on a digit that does not have any non-digit character to its left.

**Example 1:**

**Input:** s = "abc"

**Output:** "abc"

**Explanation:**

There is no digit in the string.

**Example 2:**

**Input:** s = "cb34"

**Output:** ""

**Explanation:**

First, we apply the operation on `s[2]`, and `s` becomes `"c4"`.

Then we apply the operation on `s[1]`, and `s` becomes `""`.

**Constraints:**

* `1 <= s.length <= 100`
* `s` consists only of lowercase English letters and digits.
* The input is generated such that it is possible to delete all digits.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem statement. It repeatedly finds the first digit, then finds the closest non-digit to its left, and removes both from the string. This process continues until no digits are left in the string.
**Time:** O(N^2). Let N be the length of the string and D be the number of digits. The outer `while` loop runs D times. Inside the loop, finding the digit takes up to O(N) time, and deleting a character from the `StringBuilder` also takes O(N) time. This results in a total complexity of O(D * N). In the worst case, D is proportional to N, leading to O(N^2). · **Space:** O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.
**Pros:** It is a direct translation of the problem's description, making the logic straightforward to follow.
**Cons:** Highly inefficient due to repeated scanning of the string.; The `deleteCharAt` operation on a `StringBuilder` takes linear time, leading to an overall quadratic time complexity.
### Explanation
In this method, we use a `StringBuilder` because Java's `String` objects are immutable, and we need to perform multiple deletions. The core of the algorithm is a loop that continues as long as there are digits to process.

In each iteration, we first scan the `StringBuilder` to find the index of the very first digit. If no digit is found, our work is done, and we exit the loop. If a digit is found at `digitIndex`, we then perform a second scan, this time backwards from `digitIndex - 1`, to find the first non-digit character. This gives us the `charIndex` of the character to be removed. The problem statement guarantees that such a character will always exist.

With both indices identified, we remove the two characters. A crucial detail is to remove the character at the larger index (`digitIndex`) first. This prevents the index of the second character from becoming invalid due to the shift caused by the first deletion. This entire process is repeated until the `StringBuilder` is free of digits.

```java
class Solution {
    public String clearDigits(String s) {
        StringBuilder sb = new StringBuilder(s);
        while (true) {
            int digitIndex = -1;
            // Find the first digit
            for (int i = 0; i < sb.length(); i++) {
                if (Character.isDigit(sb.charAt(i))) {
                    digitIndex = i;
                    break;
                }
            }

            // If no digit is found, we are done
            if (digitIndex == -1) {
                break;
            }

            int charIndex = -1;
            // Find the closest non-digit to the left
            for (int i = digitIndex - 1; i >= 0; i--) {
                if (!Character.isDigit(sb.charAt(i))) {
                    charIndex = i;
                    break;
                }
            }
            
            // Delete the digit first (as it has a larger index)
            sb.deleteCharAt(digitIndex);
            // Then delete the non-digit
            sb.deleteCharAt(charIndex);
        }
        return sb.toString();
    }
}
```
### Algorithm
- Convert the input string `s` into a `StringBuilder` to allow for efficient modifications.
- Enter a loop that continues indefinitely (`while(true)`).
- Inside the loop, find the index of the first character that is a digit. Let this be `digitIndex`.
- If no digit is found (`digitIndex` is -1), it means all digits have been cleared. Break the loop.
- Find the index of the closest non-digit to the left of `digitIndex`. This is done by searching backwards from `digitIndex - 1` down to 0. Let this be `charIndex`.
- Delete the characters at `digitIndex` and `charIndex` from the `StringBuilder`. It's important to delete the character with the higher index first to avoid shifting the position of the other character.
- Once the loop terminates, convert the `StringBuilder` back to a string and return it.

## Single-Pass Stack-based Approach
A more efficient approach recognizes that the operation "delete the first digit and the closest non-digit to its left" has a Last-In, First-Out (LIFO) nature. The closest non-digit to the left is always the last non-digit we have encountered so far that hasn't been deleted. This pattern is perfectly modeled by a stack.
**Time:** O(N), where N is the length of the input string. We iterate through the string once, and each operation (append or delete last character on a `StringBuilder`) takes amortized O(1) time. · **Space:** O(N), where N is the length of the input string. In the worst-case scenario (a string with no digits), the `StringBuilder` will grow to the same size as the input string.
**Pros:** Highly efficient with a linear time complexity, as it only requires a single pass over the string.; The logic is simple and clean, leveraging the stack-like behavior of a `StringBuilder`.
**Cons:** Requires extra space proportional to the number of non-digits remaining in the final string, which can be up to O(N) in the worst case.
### Explanation
This optimal solution processes the string in a single pass. We can use a `StringBuilder` as a character stack. We iterate through the input string, and for each character, we decide an action:

- If the character is a letter, we treat it as a potential part of the final result and 'push' it onto our stack by appending it to the `StringBuilder`.
- If the character is a digit, it triggers a 'delete' operation. The digit itself is discarded, and it causes the removal of the most recently added letter. In our `StringBuilder`-as-a-stack model, this corresponds to 'popping' the stack, which is done by deleting the last character of the `StringBuilder`.

Because the problem guarantees that a digit will always have a non-digit to its left to be removed, our `StringBuilder` will never be empty when we encounter a digit. After iterating through the entire string, the characters remaining in the `StringBuilder` constitute the final result.

```java
class Solution {
    public String clearDigits(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // The problem guarantees the result will not be empty here.
                if (result.length() > 0) {
                    result.deleteCharAt(result.length() - 1);
                }
            } else {
                result.append(c);
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to store the result.
- Iterate through each character `c` of the input string `s` from left to right.
- If `c` is a letter (a non-digit), append it to the `StringBuilder`.
- If `c` is a digit, it means we must remove the most recently added non-digit. This is achieved by deleting the last character from the `StringBuilder`.
- After iterating through all characters in `s`, the `StringBuilder` will contain the final string. Convert it to a `String` and return it.

# Solutions
### Java

```java
class Solution {
public
  String clearDigits(String s) {
    StringBuilder stk = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (Character.isDigit(c)) {
        stk.deleteCharAt(stk.length() - 1);
      } else {
        stk.append(c);
      }
    }
    return stk.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string clearDigits(string s) {
    string stk;
    for (char c : s) {
      if (isdigit(c)) {
        stk.pop_back();
      } else {
        stk.push_back(c);
      }
    }
    return stk;
  }
};

```

### Python

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

```