Jobs

Interviews

Discussions

Clear Digits

Easy

Asked by:

More companies

24 views

Topics:

StringsStacks

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.

Try coding it in LeetCode

Clear Digits

Easy

Asked by:

24 views

Topics:

StringsStacks

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the digits within the input string?
Is the input string guaranteed to contain only digits, or could it contain other characters?
If multiple sequences of removals lead to the same smallest number, is any valid removal sequence acceptable?
If the input string has fewer digits than the number of digits to remove, what should the output be?
Can the number of digits to remove be zero or negative?

Brute Force Solution

Approach

The brute force way to solve this problem is to explore every single possibility of removing digits from the given number. We'll systematically generate all possible numbers by removing different combinations of digits and then check if each resulting number meets the required criteria.

Here's how the algorithm would work step-by-step:

First, consider all the ways to remove just one digit from the original number, creating a set of new numbers.
Next, think about removing two digits. For each number you got after removing one digit, remove another digit in all possible ways.
Continue this process, each time removing one more digit from the numbers you generated in the previous step, until you have removed the required number of digits.
After you've created all possible numbers by removing the specified number of digits, check if each of the created numbers is valid, for example, by ensuring there are no leading zeros.
Finally, from all the valid numbers, choose the smallest one. This is your answer.

Code Implementation

def clear_digits_brute_force(number_string, digits_to_remove):
    all_possible_numbers = [number_string]

    for _ in range(digits_to_remove):
        new_possible_numbers = []

        for current_number in all_possible_numbers:
            for index_to_remove in range(len(current_number)): 
                new_number = current_number[:index_to_remove] + current_number[index_to_remove+1:]
                new_possible_numbers.append(new_number)

        all_possible_numbers = new_possible_numbers

    valid_numbers = []
    for possible_number in all_possible_numbers:
        # Ensure number does not have leading zeros and is not empty
        if (len(possible_number) > 0 and (len(possible_number) == 1 or possible_number[0] != '0')) or len(possible_number) == 0:
            valid_numbers.append(possible_number)
        elif len(possible_number) == 0:
            valid_numbers.append(possible_number)

    # Find the smallest valid number
    smallest_number = None
    for valid_number in valid_numbers:
        if len(valid_number) == 0:
            continue
        if smallest_number is None:
            smallest_number = valid_number
        else:
            smallest_number = min(smallest_number, valid_number)

    if smallest_number is None and len(valid_numbers) > 0:
        return "0"

    if smallest_number is None:
        return ""

    return smallest_number

Big(O) Analysis

Time Complexity

O(nCk) – Let n be the number of digits in the original number and k be the number of digits to remove. The algorithm essentially explores all possible combinations of removing k digits from n digits. The number of such combinations is given by the binomial coefficient n choose k, denoted as nCk, which can also be written as n! / (k! * (n-k)!). For each of these combinations, the algorithm checks for validity (e.g., leading zeros), which takes O(n-k) time in the worst case. Since generating combinations dominates the runtime, the overall time complexity is O(nCk * (n-k)), which is typically simplified to O(nCk) assuming that we fix k. In the worst case, k could be close to n/2, so we can say that O(nCk) represents the maximum time complexity.

Space Complexity

O(N choose K) – The described brute force algorithm generates all possible numbers after removing K digits from the original N-digit number. This involves storing these generated numbers, each of which contributes to the auxiliary space. The number of such possible numbers is given by the binomial coefficient "N choose K", representing the number of ways to choose K digits to remove from N digits. Therefore, the space required to store all these numbers is proportional to N choose K, where N is the number of digits in the original number and K is the number of digits to remove.

Optimal Solution

Approach

The best way to solve the 'Clear Digits' problem is to think of it like building the result one digit at a time, making sure to only keep the best result we've seen so far. We can ignore anything that would be worse than our best.

Here's how the algorithm would work step-by-step:

Start with a blank result and the given number.
Look at each digit in order from left to right.
For each digit, consider two options: either keep the digit or remove it.
If we remove a digit, update a counter of how many digits have been removed.
Compare results based on the digit that was considered and the total number of removals, and keep only the smallest number we have seen so far. If the numbers are equal, the one created by removing as few numbers as possible is smallest.
Repeat this process for each digit, always keeping track of the best number and number of removals we have seen.
If at the end, you still need to remove more digits, chop them off the end of the number. If that results in a zero or empty string, just return zero.

Code Implementation

def clear_digits(number, digits_to_remove):
    result = ""
    number_of_removals = 0

    for digit in number:
        # Maintain a monotonically increasing stack.
        while number_of_removals < digits_to_remove and result and result[-1] > digit:
            result = result[:-1]
            number_of_removals += 1

        result += digit

    # If we still need to remove digits, chop them off the end.
    while number_of_removals < digits_to_remove:
        result = result[:-1]
        number_of_removals += 1

    # Remove leading zeros.
    first_non_zero = 0
    while first_non_zero < len(result) - 1 and result[first_non_zero] == '0':
        first_non_zero += 1

    result = result[first_non_zero:]

    # Handle empty string case.
    if not result:
        return "0"

    return result

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each digit of the input number of length n. For each digit, it implicitly explores two possibilities: keeping the digit or removing it. In the worst-case scenario, the algorithm might reconsider previous choices for each digit to find the optimal result based on minimizing the resulting number and the number of removals. This nested exploration where each digit's inclusion/exclusion affects the overall state effectively leads to roughly n * n/2 operations as it considers combinations. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The described approach primarily uses a temporary string or list to build the 'best result'. In the worst-case scenario, the 'best result' could potentially store almost all the digits from the input number before removing others, leading to a string that grows linearly with the input size, N, where N is the number of digits in the input number. We also need to keep track of the 'number of removals' with a counter, which is a constant space. The storage for the 'best result' dominates the space usage, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately as there are no digits to clear.
Input string contains non-digit characters	Filter out non-digit characters, only processing the digits in the input.
Input string has all digits identical	The algorithm should still function correctly, potentially clearing all or some digits based on the specified removal criteria.
k (number of digits to clear) is zero	Return the original input string unchanged since no digits need to be removed.
k is greater than or equal to the length of the input string	Return an empty string, as all digits should be cleared.
Large input string size that may lead to stack overflow with recursive implementations	Use an iterative approach or tail-recursive optimization to prevent stack overflow for large inputs.
Integer overflow when comparing digits	Ensure that the comparison logic uses appropriate data types to prevent integer overflow issues.
Multiple valid solutions exist, but only one is required	Ensure the algorithm consistently returns the lexicographically smallest solution.

Null or empty input string

How to Handle:

Return an empty string immediately as there are no digits to clear.

Input string contains non-digit characters

How to Handle:

Filter out non-digit characters, only processing the digits in the input.

Input string has all digits identical

How to Handle:

The algorithm should still function correctly, potentially clearing all or some digits based on the specified removal criteria.

k (number of digits to clear) is zero

How to Handle:

Return the original input string unchanged since no digits need to be removed.

k is greater than or equal to the length of the input string

How to Handle:

Return an empty string, as all digits should be cleared.

Large input string size that may lead to stack overflow with recursive implementations

How to Handle:

Use an iterative approach or tail-recursive optimization to prevent stack overflow for large inputs.

Integer overflow when comparing digits

How to Handle:

Ensure that the comparison logic uses appropriate data types to prevent integer overflow issues.

Multiple valid solutions exist, but only one is required

How to Handle:

Ensure the algorithm consistently returns the lexicographically smallest solution.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the digits within the input string?
Is the input string guaranteed to contain only digits, or could it contain other characters?
If multiple sequences of removals lead to the same smallest number, is any valid removal sequence acceptable?
If the input string has fewer digits than the number of digits to remove, what should the output be?
Can the number of digits to remove be zero or negative?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider all the ways to remove just one digit from the original number, creating a set of new numbers.
Next, think about removing two digits. For each number you got after removing one digit, remove another digit in all possible ways.
Continue this process, each time removing one more digit from the numbers you generated in the previous step, until you have removed the required number of digits.
After you've created all possible numbers by removing the specified number of digits, check if each of the created numbers is valid, for example, by ensuring there are no leading zeros.
Finally, from all the valid numbers, choose the smallest one. This is your answer.

Code Implementation

def clear_digits_brute_force(number_string, digits_to_remove):
    all_possible_numbers = [number_string]

    for _ in range(digits_to_remove):
        new_possible_numbers = []

        for current_number in all_possible_numbers:
            for index_to_remove in range(len(current_number)): 
                new_number = current_number[:index_to_remove] + current_number[index_to_remove+1:]
                new_possible_numbers.append(new_number)

        all_possible_numbers = new_possible_numbers

    valid_numbers = []
    for possible_number in all_possible_numbers:
        # Ensure number does not have leading zeros and is not empty
        if (len(possible_number) > 0 and (len(possible_number) == 1 or possible_number[0] != '0')) or len(possible_number) == 0:
            valid_numbers.append(possible_number)
        elif len(possible_number) == 0:
            valid_numbers.append(possible_number)

    # Find the smallest valid number
    smallest_number = None
    for valid_number in valid_numbers:
        if len(valid_number) == 0:
            continue
        if smallest_number is None:
            smallest_number = valid_number
        else:
            smallest_number = min(smallest_number, valid_number)

    if smallest_number is None and len(valid_numbers) > 0:
        return "0"

    if smallest_number is None:
        return ""

    return smallest_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a blank result and the given number.
Look at each digit in order from left to right.
For each digit, consider two options: either keep the digit or remove it.
If we remove a digit, update a counter of how many digits have been removed.
Compare results based on the digit that was considered and the total number of removals, and keep only the smallest number we have seen so far. If the numbers are equal, the one created by removing as few numbers as possible is smallest.
Repeat this process for each digit, always keeping track of the best number and number of removals we have seen.
If at the end, you still need to remove more digits, chop them off the end of the number. If that results in a zero or empty string, just return zero.

Code Implementation

def clear_digits(number, digits_to_remove):
    result = ""
    number_of_removals = 0

    for digit in number:
        # Maintain a monotonically increasing stack.
        while number_of_removals < digits_to_remove and result and result[-1] > digit:
            result = result[:-1]
            number_of_removals += 1

        result += digit

    # If we still need to remove digits, chop them off the end.
    while number_of_removals < digits_to_remove:
        result = result[:-1]
        number_of_removals += 1

    # Remove leading zeros.
    first_non_zero = 0
    while first_non_zero < len(result) - 1 and result[first_non_zero] == '0':
        first_non_zero += 1

    result = result[first_non_zero:]

    # Handle empty string case.
    if not result:
        return "0"

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately as there are no digits to clear.
Input string contains non-digit characters	Filter out non-digit characters, only processing the digits in the input.
Input string has all digits identical	The algorithm should still function correctly, potentially clearing all or some digits based on the specified removal criteria.
k (number of digits to clear) is zero	Return the original input string unchanged since no digits need to be removed.
k is greater than or equal to the length of the input string	Return an empty string, as all digits should be cleared.
Large input string size that may lead to stack overflow with recursive implementations	Use an iterative approach or tail-recursive optimization to prevent stack overflow for large inputs.
Integer overflow when comparing digits	Ensure that the comparison logic uses appropriate data types to prevent integer overflow issues.
Multiple valid solutions exist, but only one is required	Ensure the algorithm consistently returns the lexicographically smallest solution.

Null or empty input string

How to Handle:

Return an empty string immediately as there are no digits to clear.

Input string contains non-digit characters

How to Handle:

Filter out non-digit characters, only processing the digits in the input.

Input string has all digits identical

How to Handle:

The algorithm should still function correctly, potentially clearing all or some digits based on the specified removal criteria.

k (number of digits to clear) is zero

How to Handle:

Return the original input string unchanged since no digits need to be removed.

k is greater than or equal to the length of the input string

How to Handle:

Return an empty string, as all digits should be cleared.

Large input string size that may lead to stack overflow with recursive implementations

How to Handle:

Use an iterative approach or tail-recursive optimization to prevent stack overflow for large inputs.

Integer overflow when comparing digits

How to Handle:

Ensure that the comparison logic uses appropriate data types to prevent integer overflow issues.

Multiple valid solutions exist, but only one is required

How to Handle:

Ensure the algorithm consistently returns the lexicographically smallest solution.