Scale Engineer

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
StringStack
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.

class Solution {    public String clearDigits(String s) {        StringBuilder sb = new StringBuilder(s);        while (true) {            int digitIndex = -1;            // Find the first digit            for (int i = 0; i < sb.length(); i++) {                if (Character.isDigit(sb.charAt(i))) {                    digitIndex = i;                    break;                }            }             // If no digit is found, we are done            if (digitIndex == -1) {                break;            }             int charIndex = -1;            // Find the closest non-digit to the left            for (int i = digitIndex - 1; i >= 0; i--) {                if (!Character.isDigit(sb.charAt(i))) {                    charIndex = i;                    break;                }            }                        // Delete the digit first (as it has a larger index)            sb.deleteCharAt(digitIndex);            // Then delete the non-digit            sb.deleteCharAt(charIndex);        }        return sb.toString();    }}

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.

Solutions

class Solution {public  String clearDigits(String s) {    StringBuilder stk = new StringBuilder();    for (char c : s.toCharArray()) {      if (Character.isDigit(c)) {        stk.deleteCharAt(stk.length() - 1);      } else {        stk.append(c);      }    }    return stk.toString();  }}

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 →

Next problem