Remove Digit From Number to Maximize Result

Easy

Asked by:

70 views

Topics:

StringsGreedy Algorithms

You are given a string number representing a positive integer and a character digit.

Return the resulting string after removing exactly one occurrence of digit from number such that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.

Example 1:

Input: number = "123", digit = "3"
Output: "12"
Explanation: There is only one '3' in "123". After removing '3', the result is "12".

Example 2:

Input: number = "1231", digit = "1"
Output: "231"
Explanation: We can remove the first '1' to get "231" or remove the second '1' to get "123".
Since 231 > 123, we return "231".

Example 3:

Input: number = "551", digit = "5"
Output: "51"
Explanation: We can remove either the first or second '5' from "551".
Both result in the string "51".

Constraints:

2 <= number.length <= 100
number consists of digits from '1' to '9'.
digit is a digit from '1' to '9'.
digit occurs at least once in number.

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:

Can the input string `number` contain leading zeros?
What should I return if the digit `digit` does not appear in the string `number`?
Is the input string `number` guaranteed to only contain digits, and is `digit` guaranteed to be a single digit character?
If there are multiple occurrences of the digit that, when removed, result in the same maximum number, which one should I remove (e.g., the first, the last)?
What is the maximum possible length of the `number` string?

Brute Force Solution

Approach

The brute force approach involves trying every single possible outcome. We will go through all the digits in the number and remove each one, one at a time. We then compare all the results to see which one is the biggest.

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

First, consider removing the first instance of the digit from the original number and store the resulting number.
Next, consider removing the second instance of the digit from the original number and store the resulting number.
Continue this process for every instance of the digit within the original number, storing each resulting number.
Finally, compare all the numbers generated by removing the digit, and select the largest number among them. This will be our answer.

Code Implementation

def remove_digit_to_maximize_result(number, digit):
    resulting_numbers = []

    for index in range(len(number)):
        if number[index] == digit:
            # Removing the digit at the current index
            new_number = number[:index] + number[index+1:]
            resulting_numbers.append(new_number)

    # If no instances of the digit are found.
    if not resulting_numbers:
        return number

    # Finding the largest number from all possibilities
    max_number = resulting_numbers[0]

    for resulting_number in resulting_numbers:
        # Comparing string values as integers.
        if resulting_number > max_number:
            max_number = resulting_number

    return max_number

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input number (string) of size n to find each instance of the digit to remove. For each instance found, it creates a new string of size (n-1) by removing the digit, implying a copy operation proportional to n. Since in the worst case, the digit to be removed could appear in almost every position within the input string, potentially requiring up to n removal operations, the overall time complexity is approximately n * n, which simplifies to O(n²).

Space Complexity

O(N) – The provided solution stores all the numbers generated by removing the digit. In the worst case, the digit to be removed appears in nearly every position of the original number, resulting in the creation of N-1 new strings, where N is the length of the original number. Each of these strings requires space proportional to its length, which is at most N-1. Therefore, the auxiliary space used grows linearly with the input size N, leading to O(N) space complexity.

Optimal Solution

Approach

The best way to solve this puzzle is to go through the number and find the digit we want to remove. Instead of just trying everything, we look for the removal that makes the number bigger right away. This makes the code much faster.

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

Go through the number from left to right, looking at each digit.
Every time you see the digit you want to remove, imagine taking it out and see what number you would have left.
If the new number you'd get by removing the digit is bigger than any number you've seen so far, remember it.
Keep going until you've checked every possible removal of the digit.
At the end, the number you remembered as being the biggest is the one you should return.

Code Implementation

def remove_digit(number, digit):
    best_number = ""

    for index in range(len(number)):
        if number[index] == digit:
            # Check every possible removal
            new_number = number[:index] + number[index+1:]

            # Compare with existing best
            if best_number == "" or new_number > best_number:
                best_number = new_number

    return best_number

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm iterates through the input string representing the number once. Inside the loop, it conditionally removes a digit and compares the resulting string with the current maximum. The removal operation involves string slicing, which in many languages can take O(n) time in the worst case (if implemented via copy), but since the core logic emphasizes finding the first digit to remove that INCREASES the value, it is optimized such that it can return as soon as it finds a larger number after removing the particular digit from the original number. String comparison is bounded by n. Although there is string slicing within the loop and implicit comparison between string formed by removing digits, the algorithm only goes through the string once (at most), so the dominant factor is the single pass through the number. Hence, the overall time complexity is O(n), where n is the length of the number string.

Space Complexity

O(N) – The algorithm iterates through the input number (string) and potentially stores the largest number found so far. The largest number found is stored as a string, which in the worst-case scenario, can be a string of length N-1, where N is the length of the input number string. Therefore, the auxiliary space required to store the largest string found is proportional to N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
number is null or empty	Return an empty string immediately as no digit can be removed.
digit is null or empty	Return the original number string as no digit is specified to remove.
digit is not present in the number	Return the original number as no valid removal can occur.
number consists of a single digit and that digit is the target digit	Return an empty string after removing the only digit.
number contains multiple occurrences of the digit	Iterate from left to right, and remove the first digit that results in a larger number, comparing lexicographically.
number contains only the digit and multiple occurrences of it	Remove the leftmost digit, since all resulting numbers are the same length and removing any digit leads to a valid result.
digit is a character not representable as an integer	Treat it as a character, compare it lexicographically, or throw an exception if appropriate based on requirements.
number is very large and may cause performance issues with string manipulation	Consider using StringBuilder for efficient string manipulation to avoid excessive object creation.

number is null or empty

How to Handle:

Return an empty string immediately as no digit can be removed.

digit is null or empty

How to Handle:

Return the original number string as no digit is specified to remove.

digit is not present in the number

How to Handle:

Return the original number as no valid removal can occur.

number consists of a single digit and that digit is the target digit

How to Handle:

Return an empty string after removing the only digit.

number contains multiple occurrences of the digit

How to Handle:

Iterate from left to right, and remove the first digit that results in a larger number, comparing lexicographically.

number contains only the digit and multiple occurrences of it

How to Handle:

Remove the leftmost digit, since all resulting numbers are the same length and removing any digit leads to a valid result.

digit is a character not representable as an integer

How to Handle:

Treat it as a character, compare it lexicographically, or throw an exception if appropriate based on requirements.

number is very large and may cause performance issues with string manipulation

How to Handle:

Consider using StringBuilder for efficient string manipulation to avoid excessive object creation.