Teaching Kids Programming – Using Stack to Remove Digits and Characters on the Left

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string s. Your task is to remove all digits by doing this operation repeatedly:

1. Delete the first digit and the closest non-digit character to its left.
2. Return the resulting string after removing all digits.

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.

Using Stack to Remove Digits and Characters on the Left

We use a stack to emulate the process. When we see a character, we push it to the top of the stack. When we see a digit, we remove the top of the stack (if the stack is not empty). We continue the process until we iterate over all the characters in the string. Then we join the characters to a string. The time/space complexity is O(N) where N is the number of the characters in the given string.

A stack is a First In Last Out Data Structure while a queue is First In First Out. And, we also have First In Priority Out – aka the Priority Queue.

1
2
3
4
5
6
7
8
9
10

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

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

–EOF (The Ultimate Computing & Technology Blog) —