We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Clear Digits

Difficulty: Easy

Problem Description

You are given a string s. Your task is to remove all digits by deleting the first digit and the closest non-digit character to its left repeatedly. Return the resulting string after removing all digits.

Key Insights

  • The operation can only be performed on a digit that has a non-digit character to its left.
  • The closest non-digit character to the left of a digit must be removed alongside the digit.
  • A stack data structure can be utilized to manage the characters in the string as we process them.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Each character is processed once. Space Complexity: O(n), in the worst case, for the stack to store the resulting characters.

Solution

To solve the problem, we can use a stack to keep track of the characters in the string. We will iterate through each character of the string:

  1. If the character is a digit, we check if the stack is not empty. If it is not empty, we pop the last character from the stack (the closest non-digit character) and do not push the digit onto the stack.
  2. If the character is not a digit, we simply push it onto the stack.
  3. After processing all characters, we join the characters in the stack to form the resulting string.

This approach ensures that we efficiently manage the removal of digits and their corresponding non-digit characters.

Code Solutions

def clear_digits(s: str) -> str:
    stack = []
    for char in s:
        if char.isdigit():
            if stack:  # Only pop if there's a non-digit character
                stack.pop()  # Remove the closest non-digit character
        else:
            stack.append(char)  # Push non-digit characters onto the stack
    return ''.join(stack)  # Join remaining characters to form the result
← Back to All Questions