3174. Clear Digits

EasyStackStringSimulation

Problem Description

You are given a string s. Your task is to remove all digits by repeatedly performing the following operation: delete the first digit encountered and the closest non-digit character to its left. Once all the digits have been removed in this manner, return the resulting string.

Intuition

The key to solving this problem is to simulate the removal process using a structure that efficiently supports operations at the end, such as a stack. As we iterate through the string, each time we encounter a digit, we know we need to remove the closest non-digit character to its left. By using a stack, when a digit is encountered, we can simply pop the top element (which represents the last non-digit character added and hence the closest to the left) and skip adding the digit itself, effectively removing both the non-digit and the digit. If a character is not a digit, we push it onto the stack. After processing all characters, the stack will contain all surviving non-digit characters in their original order, which we then join back into the final resulting string.

Learn more about Stack patterns.

Solution Approach

To solve this problem, we employ a stack-based simulation. Here’s the detailed breakdown of the solution:

Initialize a Stack: Start by creating an empty stack stk to assist in managing the characters as we process the string.
Iterate Over the String: Traverse each character c in the string s.
- If the Character is a Digit:
  - We remove (pop) the top element from the stack. This top element is the closest non-digit character to the left of the digit and has to be deleted as per the problem statement.
  - We do not add the digit to the stack since the digit itself needs to be removed.
- If the Character is Not a Digit:
  - Simply push (add) this character onto the stack, as it might either survive till the end or potentially be removed by a future digit.
Form the Resulting String: After processing all characters in the string, the stack stk contains all characters that are not removed. These are the non-digit characters that were not closest to any digit and hence remain. Convert the stack into a string using "".join(stk) to get the final result.

This approach efficiently applies the required operations on the string using the stack structure, allowing us to achieve the desired result in a single pass through the input string with optimal time complexity.

Here is the solution code encapsulated in the Solution class:

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)

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string s = "ab1c2d3".

Step 1: Initialize a Stack

Start with an empty stack: stk = [].

Step 2: Iterate Over the String

Process each character in s:
- For character a:
  - It is not a digit, so push it onto the stack: stk = ['a'].
- For character b:
  - It is not a digit, so push it onto the stack: stk = ['a', 'b'].
- For character 1:
  - This is a digit. Pop from stack, removing b: stk = ['a'].
  - Digit 1 is not added to the stack.
- For character c:
  - It is not a digit, so push it onto the stack: stk = ['a', 'c'].
- For character 2:
  - This is a digit. Pop from stack, removing c: stk = ['a'].
  - Digit 2 is not added to the stack.
- For character d:
  - It is not a digit, so push it onto the stack: stk = ['a', 'd'].
- For character 3:
  - This is a digit. Pop from stack, removing d: stk = ['a'].
  - Digit 3 is not added to the stack.

Step 3: Form the Resulting String

The stack stk now contains the resulting non-digit characters that were not removed due to any digits: stk = ['a'].
Convert the stack to a string: result = "".join(stk), resulting in "a".

Thus, the final output is "a".

Solution Implementation

1class Solution:
2    def clearDigits(self, s: str) -> str:
3        # Initialize an empty stack to keep track of characters
4        stack = []
5      
6        # Iterate over each character in the input string
7        for char in s:
8            # If the character is a digit, pop the last element from the stack
9            if char.isdigit():
10                if stack:  # Ensure the stack is not empty before popping
11                    stack.pop()
12            else:
13                # If the character is not a digit, push it onto the stack
14                stack.append(char)
15      
16        # Join all characters in the stack to form the resultant string
17        return "".join(stack)
18

1class Solution {
2    public String clearDigits(String s) {
3        // Use a StringBuilder as a mutable sequence to construct the output string.
4        StringBuilder resultBuilder = new StringBuilder();
5      
6        // Iterate through each character in the input string.
7        for (char character : s.toCharArray()) {
8            // Check if the character is a digit.
9            if (Character.isDigit(character)) {
10                // If it is a digit, remove the last character from the StringBuilder if it has any characters.
11                if (resultBuilder.length() > 0) {
12                    resultBuilder.deleteCharAt(resultBuilder.length() - 1);
13                }
14            } else {
15                // If it's not a digit, append the character to the StringBuilder.
16                resultBuilder.append(character);
17            }
18        }
19      
20        // Convert the StringBuilder to a String and return the result.
21        return resultBuilder.toString();
22    }
23}
24

1class Solution {
2public:
3    string clearDigits(string s) {
4        string stack; // Initialize an empty string to simulate a stack
5        for (char c : s) { // Loop through each character in the input string
6            if (isdigit(c)) { // Check if the current character is a digit
7                if (!stack.empty()) { // Ensure there's something to pop
8                    stack.pop_back(); // Remove the last character from the stack
9                }
10            } else { // If the character is not a digit
11                stack.push_back(c); // Add the non-digit character to the stack
12            }
13        }
14        return stack; // Return the resulting stack as a string
15    }
16};
17

1// This function removes a character from the result stack for every digit found in the input string.
2function clearDigits(s: string): string {
3    const stack: string[] = []; // Initialize an empty stack to collect non-digit characters.
4  
5    // Iterate over each character in the input string.
6    for (const char of s) {
7        // Check if the character is a digit.
8        if (!isNaN(parseInt(char))) {
9            // If it's a digit, remove the last added non-digit character from the stack.
10            stack.pop();
11        } else {
12            // If it's not a digit, add the character to the stack.
13            stack.push(char);
14        }
15    }
16  
17    // Join the stack into a string and return as the result.
18    return stack.join('');
19}
20

Time and Space Complexity

The time complexity is O(n) because the algorithm iterates through each character of the string s once. For each character, the operations performed are either appending to the list stk or popping from it, both of which are constant time operations O(1).

The space complexity is also O(n) because, in the worst case, the list stk may store all characters from the input string s, especially when s contains no digits. Consequently, the auxiliary space required for stk grows linearly with the size of the input string.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don’t know