3174. Clear Digits

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.

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.

Approach 01:

class Solution {
  public:
    string clearDigits(string inputStr) {
        vector<char> resultStack;
        
        for (char currentChar : inputStr) {
            if (!resultStack.empty() && isalpha(resultStack.back()) && isdigit(currentChar)) {
                resultStack.pop_back();
            } else if (!resultStack.empty() && isdigit(resultStack.back()) && isalpha(currentChar)) {
                resultStack.pop_back();
            } else {
                resultStack.push_back(currentChar);
            }
        }

        return string(resultStack.begin(), resultStack.end());
    }
};

class Solution:
    def clearDigits(self, inputStr: str) -> str:
        resultStack = []
        
        for currentChar in inputStr:
            if resultStack and resultStack[-1].isalpha() and currentChar.isdigit():
                resultStack.pop()
            elif resultStack and resultStack[-1].isdigit() and currentChar.isalpha():
                resultStack.pop()
            else:
                resultStack.append(currentChar)
        
        return ''.join(resultStack)

Time Complexity:

• Iteration Over the String:

  Each character in the input string is processed once, leading to a complexity of \( O(N) \), where \( N \) is the length of the string.

• Stack Operations:

  Each character is pushed or popped from the stack at most once, which is an \( O(1) \) operation.

• Overall Time Complexity:

  \( O(N) \), as each character is handled in constant time.

Space Complexity:

• Stack Storage:

  In the worst case, all characters are stored in the stack, leading to \( O(N) \) space usage.

• Final String Construction:

  The result string is constructed from the stack, requiring additional \( O(N) \) space.

• Overall Space Complexity:

  \( O(N) \), as the stack and the output string both use linear space.