Problem Statement & Formal Constraints

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.

Algorithmic Mechanics: Digits as LIFO Backspace Operators

The problem definition mandates that every digit eliminates the most recently encountered non-digit character to its left. This behavior corresponds directly to a Last-In, First-Out (LIFO) stack mechanism:

• When encountering a letter ('a' through 'z'), push it onto the character stack.
• When encountering a digit ('0' through '9'), pop the topmost letter from the stack.

By simulating this process from left to right, all digits are removed, and matched non-digit characters are cleanly discarded in a single $O(N)$ pass.

Approach 1: In-Place Two-Pointer Compaction (Optimal C++)

Rather than allocating an explicit dynamic std::stack<char> that requires reverse reconstruction, we can mutate the string directly in-place using a write pointer index:

#include <string>

class Solution {
public:
    std::string clearDigits(std::string s) {
        int writeIndex = 0;

        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                // Digit encountered: pop the previous character by decrementing write pointer
                if (writeIndex > 0) {
                    writeIndex--;
                }
            } else {
                // Letter encountered: write to current position and advance pointer
                s[writeIndex++] = c;
            }
        }

        // Truncate string to valid length
        s.resize(writeIndex);
        return s;
    }
};

Approach 2: TypeScript Array Stack Implementation

In TypeScript, JavaScript arrays provide native $O(1)$ amortized push() and pop() methods:

/**
 * Removes all digits and closest preceding non-digit characters using a character stack.
 * Time Complexity: O(N) single-pass
 * Space Complexity: O(N) output string buffer
 */
export function clearDigits(s: string): string {
  const stack: string[] = [];

  for (let i = 0; i < s.length; i++) {
    const code = s.charCodeAt(i);
    // ASCII codes for '0' to '9' are 48 through 57
    if (code >= 48 && code <= 57) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }

  return stack.join('');
}

Complexity Evaluation Matrix

The table below compares algorithmic implementations for LeetCode 3174:

Real-World Full-Stack Engineering Applications

LIFO character stack compaction patterns apply across multiple production web systems:

• Terminal & Command-Line Backspace Handling: Interpreting ANSI terminal escape codes where  or delete codes erase preceding characters in interactive shells.
• Lexical Sanitization in Markdown Parsers: Processing markdown escape characters (such as escaping asterisks *bold*) in document tokenizers.
• Undo/Redo Text Buffer Buffering: Managing transaction rollback log streams in rich-text web editors.

Frequently Asked Questions

Can multiple consecutive digits cause an underflow error?

No. The problem statement explicitly guarantees that the input is valid and generated such that it is always possible to delete all digits. A digit is never encountered when the stack is empty.

Why is in-place string mutation faster than array stack join in JavaScript?

In JavaScript/V8, strings are immutable primitive types, so in-place character index mutation is not directly supported on strings. However, in C++ or Rust, std::string is mutable, allowing $O(1)$ auxiliary space mutation without copying.

Why check charCodeAt(i) instead of regular expressions?

Evaluating numeric character boundaries (code >= 48 && code <= 57) compiles to direct integer comparison instructions, executing significantly faster than loading and executing a regex engine (/d/).

What is the maximum recursion depth if implemented with DFS?

If implemented recursively, the call stack depth would reach $O(N)$. Iterative simulation is preferred to guarantee constant call-stack memory.

Conclusion & Performance Takeaways

LeetCode 3174 illustrates how recognizing LIFO backspace dynamics simplifies string manipulation. By replacing quadratic string splicing with a single-pass stack simulation or in-place write pointer, engineers achieve optimal $O(N)$ linear time complexity.