Clear Digits

Easy

#2819Time: O(N^2). Let N be the length of the string and D be the number of digits. The outer `while` loop runs D times. Inside the loop, finding the digit takes up to O(N) time, and deleting a character from the `StringBuilder` also takes O(N) time. This results in a total complexity of O(D * N). In the worst case, D is proportional to N, leading to O(N^2).Space: O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.1 company

Data structures

String Stack

Companies

Flexera

Prompt

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.

Note that the operation cannot be performed on a digit that does not have any non-digit character to its left.

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem statement. It repeatedly finds the first digit, then finds the closest non-digit to its left, and removes both from the string. This process continues until no digits are left in the string.

Algorithm

Convert the input string s into a StringBuilder to allow for efficient modifications.
Enter a loop that continues indefinitely (while(true)).
Inside the loop, find the index of the first character that is a digit. Let this be digitIndex.
If no digit is found (digitIndex is -1), it means all digits have been cleared. Break the loop.
Find the index of the closest non-digit to the left of digitIndex. This is done by searching backwards from digitIndex - 1 down to 0. Let this be charIndex.
Delete the characters at digitIndex and charIndex from the StringBuilder. It's important to delete the character with the higher index first to avoid shifting the position of the other character.
Once the loop terminates, convert the StringBuilder back to a string and return it.

Walkthrough

In this method, we use a StringBuilder because Java's String objects are immutable, and we need to perform multiple deletions. The core of the algorithm is a loop that continues as long as there are digits to process.

In each iteration, we first scan the StringBuilder to find the index of the very first digit. If no digit is found, our work is done, and we exit the loop. If a digit is found at digitIndex, we then perform a second scan, this time backwards from digitIndex - 1, to find the first non-digit character. This gives us the charIndex of the character to be removed. The problem statement guarantees that such a character will always exist.

With both indices identified, we remove the two characters. A crucial detail is to remove the character at the larger index (digitIndex) first. This prevents the index of the second character from becoming invalid due to the shift caused by the first deletion. This entire process is repeated until the StringBuilder is free of digits.

1class Solution {2    public String clearDigits(String s) {3        StringBuilder sb = new StringBuilder(s);4        while (true) {5            int digitIndex = -1;6            // Find the first digit7            for (int i = 0; i < sb.length(); i++) {8                if (Character.isDigit(sb.charAt(i))) {9                    digitIndex = i;10                    break;11                }12            }13 14            // If no digit is found, we are done15            if (digitIndex == -1) {16                break;17            }18 19            int charIndex = -1;20            // Find the closest non-digit to the left21            for (int i = digitIndex - 1; i >= 0; i--) {22                if (!Character.isDigit(sb.charAt(i))) {23                    charIndex = i;24                    break;25                }26            }27            28            // Delete the digit first (as it has a larger index)29            sb.deleteCharAt(digitIndex);30            // Then delete the non-digit31            sb.deleteCharAt(charIndex);32        }33        return sb.toString();34    }35}

Complexity

Time

O(N^2). Let N be the length of the string and D be the number of digits. The outer `while` loop runs D times. Inside the loop, finding the digit takes up to O(N) time, and deleting a character from the `StringBuilder` also takes O(N) time. This results in a total complexity of O(D * N). In the worst case, D is proportional to N, leading to O(N^2).

Space

O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.

Trade-offs

Pros

It is a direct translation of the problem's description, making the logic straightforward to follow.

Cons

Highly inefficient due to repeated scanning of the string.
The deleteCharAt operation on a StringBuilder takes linear time, leading to an overall quadratic time complexity.

A more efficient approach recognizes that the operation "delete the first digit and the closest non-digit to its left" has a Last-In, First-Out (LIFO) nature. The closest non-digit to the left is always the last non-digit we have encountered so far that hasn't been deleted. This pattern is perfectly modeled by a stack.

Algorithm

Initialize an empty StringBuilder to store the result.
Iterate through each character c of the input string s from left to right.
If c is a letter (a non-digit), append it to the StringBuilder.
If c is a digit, it means we must remove the most recently added non-digit. This is achieved by deleting the last character from the StringBuilder.
After iterating through all characters in s, the StringBuilder will contain the final string. Convert it to a String and return it.

Walkthrough

This optimal solution processes the string in a single pass. We can use a StringBuilder as a character stack. We iterate through the input string, and for each character, we decide an action:

If the character is a letter, we treat it as a potential part of the final result and 'push' it onto our stack by appending it to the StringBuilder.
If the character is a digit, it triggers a 'delete' operation. The digit itself is discarded, and it causes the removal of the most recently added letter. In our StringBuilder-as-a-stack model, this corresponds to 'popping' the stack, which is done by deleting the last character of the StringBuilder.

Because the problem guarantees that a digit will always have a non-digit to its left to be removed, our StringBuilder will never be empty when we encounter a digit. After iterating through the entire string, the characters remaining in the StringBuilder constitute the final result.

1class Solution {2    public String clearDigits(String s) {3        StringBuilder result = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (Character.isDigit(c)) {6                // The problem guarantees the result will not be empty here.7                if (result.length() > 0) {8                    result.deleteCharAt(result.length() - 1);9                }10            } else {11                result.append(c);12            }13        }14        return result.toString();15    }16}

Complexity

Time

O(N), where N is the length of the input string. We iterate through the string once, and each operation (append or delete last character on a `StringBuilder`) takes amortized O(1) time.

Space

O(N), where N is the length of the input string. In the worst-case scenario (a string with no digits), the `StringBuilder` will grow to the same size as the input string.

Trade-offs

Pros

Highly efficient with a linear time complexity, as it only requires a single pass over the string.
The logic is simple and clean, leveraging the stack-like behavior of a StringBuilder.

Cons

Requires extra space proportional to the number of non-digits remaining in the final string, which can be up to O(N) in the worst case.

Solutions

Solution

1class Solution {2public3  String clearDigits(String s) {4    StringBuilder stk = new StringBuilder();5    for (char c : s.toCharArray()) {6      if (Character.isDigit(c)) {7        stk.deleteCharAt(stk.length() - 1);8      } else {9        stk.append(c);10      }11    }12    return stk.toString();13  }14}

1class Solution {2public:3  string clearDigits(string s) {4    string stk;5    for (char c : s) {6      if (isdigit(c)) {7        stk.pop_back();8      } else {9        stk.push_back(c);10      }11    }12    return stk;13  }14};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem