Problem

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.

Examples

Example 1:

1
2
3
4

Input: s = "abc"
Output: "abc"
Explanation:
There is no digit in the string.

Example 2:

1
2
3
4
5

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.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive with mutable String manipulation

The method involves iterating through the string once, modifying it directly to remove digits and their closest preceding non-digit characters.

Here is the approach:

  1. Iterate through the string using an index i.
  2. When a digit is found, remove it and the closest non-digit to its left.
  3. Adjust the index to account for changes in the string length.
  4. Continue this process until the end of the string is reached.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {

    public String clearDigits(String s) {
        int i = 0;

        StringBuilder sb = new StringBuilder(s);

        // Until we reach the end of the string
        while (i < sb.length()) {
            if (Character.isDigit(sb.charAt(i))) {
                // Remove the digit from the string
                sb.deleteCharAt(i);
                // If there is a character to the left of the digit, remove it
                if (i > 0) {
                    sb.deleteCharAt(i - 1);
                    // Adjust the index to account for the removed character
                    i--;
                }
            } else {
                // Move to the next character if it's not a digit
                i++;
            }
        }
        return sb.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def clearDigits(self, s: str) -> str:
        i: int = 0
        sb: list[str] = list(s)

        # Until we reach the end of the string
        while i < len(sb):
            if sb[i].isdigit():
                # Remove the digit from the list
                del sb[i]
                # If there is a character to the left of the digit, remove it
                if i > 0:
                    del sb[i - 1]
                    # Adjust index to account for the removed character
                    i -= 1
            else:
                # Move to the next character if it's not a digit
                i += 1

        return ''.join(sb)

Complexity

  • ⏰ Time complexity: O(n^2) in worst case. Because for each digit, performing an “erase” operation involves shifting characters, which has a time complexity of O(n). And in worst case, there will be n/2 digits in the string leading to time complexity of O(n^2).
  • 🧺 Space complexity: O(n). The space complexity is linear due to the use of a StringBuilder in Java or a list in Python for storing the string.

Method 2 - Using mutable string as a stack

Using a stack-like structure allows us to efficiently remove the last added non-digit character whenever we encounter a digit.

Here is the approach:

  1. Create an empty StringBuilder in Java or a list in Python to use as a stack.
  2. Iterate through the input string character by character.
  3. If the current character is a digit and the stack is not empty, remove the last character from the stack.
  4. If the current character is not a digit, add it to the stack.
  5. After processing all characters, convert the stack back to a string and return it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {

    public String clearDigits(String s) {
        StringBuilder ans = new StringBuilder();

        // Iterate through each character in the input string
        for (int i = 0; i < s.length(); i++) {
            // if the current character is a digit and if the answer has characters
            if (Character.isDigit(s.charAt(i)) && ans.length() != 0) {
                // If true, remove the last character from the answer
                ans.setLength(ans.length() - 1);
            } else {
                // else if it is a char, add it to the answer
                ans.append(s.charAt(i));
            }
        }

        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def clearDigits(self, s: str) -> str:
        ans = []

        # Iterate through each character in the input string
        for i in range(len(s)):
            # if the current character is a digit and if the stack is not empty
            if s[i].isdigit() and ans:
                # If true, remove the last character from the stack
                ans.pop()
            else:
                # else if it is a char, add it to the stack
                ans.append(s[i])

        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n). Each character in the string is processed once, and stack operations (push and pop) are O(1) operations. Therefore, the overall time complexity is linear.
  • 🧺 Space complexity: O(n). The space complexity is linear due to using a stack-like structure to store the resulting characters.

Method 3 - Two Pointer Technique

Using a two-pointer technique allows for efficient in-place modification of the string. One pointer iterates through the string, and the other pointer keeps track of the position where the next valid character should be placed.

Here is the approach:

  1. Use an array of characters to manipulate the string.
  2. Traverse the string with one pointer i.
  3. Maintain another pointer j that tracks the position of the next valid character in the result.
  4. If a digit is found, decrement the pointer j (if it’s not already 0).
  5. If a non-digit character is found, place it at the position j and increment j.
  6. Finally, convert the mutable array back to a string using only the valid length determined by j.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
    public String clearDigits(String s) {
        int j = 0;
        char[] ans = s.toCharArray();

        // Iterate through each character in the input string
        for (int i = 0; i < s.length(); i++) {
            // if the current character is a digit and there is at least one character in the result
            if (Character.isDigit(s.charAt(i)) && j > 0) {
                // If a digit, decrease j to effectively remove the previous character
                j = Math.max(j - 1, 0);
            } else {
                // else if it is a char, store it in the result array
                ans[j++] = s.charAt(i);
            }
        }

        // Create a new string from the result array up to the valid length
        return new String(ans, 0, j);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def clearDigits(self, s: str) -> str:
        j: int = 0
        ans: list[str] = list(s)

        # Iterate through each character in the input string
        for i in range(len(s)):
            # if the current character is a digit and there is at least one character in the result
            if s[i].isdigit() and j > 0:
                # If a digit, decrease j to effectively remove the previous character
                j = max(j - 1, 0)
            else:
                # else if it is a char, store it in the result array
                ans[j] = s[i]
                j += 1

        # Create a new string from the result array up to the valid length
        return ''.join(ans[:j])

Complexity

  • ⏰ Time complexity: O(n). Each character in the string is processed once, making the overall time complexity linear.
  • 🧺 Space complexity: O(n) due to using an array to store the modified string.