#3174

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Clear Digits

Remove all digits from a given string by applying a repeated operation to form the final string without digits.

Problem Statement

You are given a string s, and your task is to remove all digits from the string by applying the following operation repeatedly: If s[i] is a digit, remove the nearest unmarked non-digit character before it. Continue this until all digits are removed.

Return the final string after performing this operation until no digits remain. The operation ensures that each digit's nearest unmarked non-digit character to the left is removed before any further actions.

Examples

Example 1

Input: s = "abc"

Output: "abc"

There is no digit in the string.

Example 2

Input: s = "cb34"

Output: ""

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.

Solution Approach

Iterate through the string

Process the string s from left to right. For each character, if it is a digit, locate the nearest non-digit character to its left that hasn't already been marked for removal.

Use a stack for management

A stack helps manage the removal process. For every non-digit, push it onto the stack. When a digit is encountered, pop the nearest non-digit character off the stack.

Finalize the string

After processing all characters, convert the stack back to a string by joining the remaining non-digit characters and returning the final result.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because each character is processed exactly once. The space complexity is O(1), as no extra space is required beyond the stack for managing the string.

What Interviewers Usually Probe

Candidate can effectively apply stack-based state management to solve the problem.
Candidate is familiar with processing strings efficiently from left to right.
Candidate can relate the stack operations to real-world scenarios or other algorithms.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark digits that should be removed or removing too many characters.
Not handling edge cases like no digits in the string or consecutive digits.
Misunderstanding the operation to apply on digits and non-digits in the string.

Follow-up variants

Consider strings with more complex patterns or large numbers of consecutive digits.
Change the constraints by allowing uppercase letters or symbols in the string.
Optimize for different input sizes or test for time efficiency in edge cases.

FAQ

How do I remove digits from a string in the 'Clear Digits' problem?

Use a stack-based approach: for each character, if it's a digit, remove the nearest non-digit character before it. Continue until all digits are removed.

What pattern does the 'Clear Digits' problem follow?

It follows a stack-based state management pattern where you manage characters from left to right, handling digits and non-digits efficiently.

How does stack management help solve the problem?

A stack helps keep track of non-digit characters and removes the nearest ones when a digit is encountered, ensuring the problem is solved efficiently.

What is the time complexity of solving the 'Clear Digits' problem?

The time complexity is O(n), where n is the length of the string, as each character is processed exactly once.

What are some common mistakes in solving this problem?

Mistakes include failing to properly mark digits for removal, not handling edge cases like no digits, and misunderstanding the string processing order.

terminal

Solution

Solution 1: Stack + Simulation

We use a stack `stk` to simulate this process. We traverse the string `s`. If the current character is a digit, we pop the top element from the stack. Otherwise, we push the current character into the stack.

1

2

3

4

5

6

7

8

9

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)

Continue Practicing

#3412 find mirror score of a string #3561 resulting string after adjacent removals #2696 minimum string length after removing substrings