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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Clear Digits

Number: 3447

Difficulty: Easy

Paid? No

Companies: Google, Meta, Flexera

Problem Description

Given a string s containing only lowercase English letters and digits, repeatedly perform the following operation: find the first digit in the string and delete that digit together with its closest non-digit character to its left. Continue performing these operations until there are no digits left in s. Return the resulting string. Note that the operation cannot be applied if there is no non-digit character to the left of a digit. The input is generated such that it is always possible to delete all digits.

Key Insights

  • We need to simulate an operation that removes a digit and its adjacent non-digit to its left.
  • A stack is a natural data structure for this simulation since it lets us access the last added (closest left) character.
  • By iterating through the string and using the stack to pair non-digits with the subsequent digit, we can effectively "cancel" out both characters.
  • The process ensures that each digit leads to removal of exactly one preceding non-digit (if available).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we iterate through the string once. Space Complexity: O(n), in the worst case when no digits are encountered (or before they are canceled).

Solution

The solution leverages a stack to simulate the operations. As we traverse the string from left to right:

  1. When encountering a non-digit character, push it onto the stack.
  2. When encountering a digit, pop the most recent non-digit character from the stack (which represents the closest non-digit to its left) and ignore the digit.
  3. Continue this process to ensure all digits are paired and removed along with their corresponding non-digits.
  4. Finally, the remaining characters in the stack form the resulting string.

This simulation correctly mimics the specified deletion order and ensures that all digits are removed as required.

Code Solutions

# Python solution with line-by-line comments
def clearDigits(s: str) -> str:
    # Initialize an empty list to use as a stack for non-digit characters
    stack = []
    # Process each character in the input string
    for char in s:
        # Check if the character is a digit
        if char.isdigit():
            # When a digit is encountered, pop the last non-digit from the stack if available
            if stack:
                stack.pop()
        else:
            # If the character is a non-digit, push it onto the stack
            stack.append(char)
    # Join the remaining characters in the stack to form the final string
    return ''.join(stack)

# Example usage:
s = "cb34"
result = clearDigits(s)
print(result)  # Output is ""
← Back to All Questions