Clear Digits

easy string stack simulation

Problem

You are given a string s of lowercase letters and digits. Repeatedly delete the first digit together with the closest non-digit character to its left. Return the string left after every digit is removed. The input always allows all digits to be deleted.

Inputs = "cb34"

Output""

Apply on s[2] (the 3) → "c4"; then on s[1] (the 4) → "".

s (letters and digits)

def clearDigits(s):
    stack = []                      # kept non-digit characters
    for ch in s:
        if ch.isdigit():
            if stack:               # delete closest non-digit on the left
                stack.pop()
        else:
            stack.append(ch)        # keep this character for now
    return "".join(stack)

function clearDigits(s) {
  const stack = [];                       // kept non-digit characters
  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      if (stack.length) stack.pop();       // delete closest non-digit left
    } else {
      stack.push(ch);                      // keep this character for now
    }
  }
  return stack.join("");
}

String clearDigits(String s) {
    StringBuilder stack = new StringBuilder();   // kept non-digits
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (Character.isDigit(ch)) {
            if (stack.length() > 0)              // delete closest left
                stack.deleteCharAt(stack.length() - 1);
        } else {
            stack.append(ch);                    // keep for now
        }
    }
    return stack.toString();
}

string clearDigits(string s) {
    string stack;                         // kept non-digit characters
    for (char ch : s) {
        if (isdigit(ch)) {
            if (!stack.empty())            // delete closest non-digit left
                stack.pop_back();
        } else {
            stack.push_back(ch);           // keep this character for now
        }
    }
    return stack;
}

Explanation

Each digit erases the closest surviving non-digit to its left. "Closest surviving" is exactly the behaviour of a stack: the most recently kept letter sits on top, so popping the stack removes precisely the character a digit would pair with.

We scan s once from left to right. When we meet a non-digit we push it onto the stack. When we meet a digit we pop the top, which deletes both that digit and the letter it cancels in one move — the digit itself is never stored.

Because the problem guarantees every digit can be deleted, the stack is never empty when a digit arrives in valid input; the if stack guard simply keeps the code safe. After the pass, whatever remains on the stack is the answer, read bottom-to-top.

Example: s = "cb34". Push c, push b (stack [c, b]). The 3 pops b → [c]. The 4 pops c → []. The result is the empty string "".

Time: O(n) Space: O(n)