SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The task requires us to remove all digits from the string s by repeatedly deleting the first digit and the closest non-digit character to its left. This operation needs to be performed until there are no more digits left in the string. The intuition behind solving this problem involves using a stack data structure to efficiently manage the removal of characters as specified.

By using a stack, we can easily keep track of non-digit characters and perform the removal operation in a Last-In-First-Out (LIFO) manner. This approach helps in efficiently removing the closest non-digit character to the left of a digit.

Approach

1. Initialization: Create an empty stack to store non-digit characters.

2. Iterate through the string: Traverse each character in the string s.

   • If the character is a non-digit, push it onto the stack.
   • If the character is a digit:
     • If the stack is not empty, pop the last character from the stack (this represents the closest non-digit character to the left).
     • Continue to the next character.

3. Result Construction: After processing all characters in the string, the stack will contain only the non-digit characters that were not removed. Convert the stack to a string and return it.

By following this approach, we ensure that we are removing characters as specified and maintaining the order of characters in the resulting string.

Complexity

Time Complexity:

• The time complexity of this approach is O(n), where n is the length of the input string s. This is because we process each character exactly once.

Space Complexity:

• The space complexity is O(n) in the worst case, where the stack stores all non-digit characters from the input string s.

Code

C++

class Solution {
public:
    string clearDigits(string s) {
        vector<char> stack;
        for (char c : s) {
            if (c < '0' || c > '9') {
                stack.push_back(c);
            } else if (!stack.empty()) {
                stack.pop_back();
            }
        }
        return string(stack.begin(), stack.end());
    }
};

Python

class Solution:
    def clearDigits(self, s: str) -> str:
        stack = []
        for c in s:
            if not c.isdigit():
                stack.append(c)
            elif stack:
                stack.pop()
        return ''.join(stack)

Java

class Solution {
    public String clearDigits(String s) {
        StringBuilder stack = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') {
                stack.append(c);
            } else if (stack.length() > 0) {
                stack.deleteCharAt(stack.length() - 1);
            }
        }
        return stack.toString();
    }
}

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var clearDigits = function (s) {
    var stack = [];
    for (var i = 0; i < s.length; i++) {
        if ('0123456789'.indexOf(s[i]) < 0) {
            stack.push(s[i]);
        } else {
            stack.pop();
        }
    }
    return stack.join('');
};