Remove Digit From Number to Maximize Result

Difficulty: Easy | Acceptance: 48.50% | Paid: No Topics: String, Greedy, Enumeration

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.

• Examples
• Constraints
• Brute Force Enumeration
• Greedy Approach

Examples

Example 1:

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 2:

Input: number = "551", digit = "5"
Output: "51"
Explanation: We can remove the first '5' to get "51" or remove the second '5' to get "51".
Since both are equal, we return "51".

Example 3:

Input: number = "123141", digit = "1"
Output: "23141"
Explanation: We can remove the first '1' to get "23141", remove the second '1' to get "12341", or remove the third '1' to get "12314".
Since 23141 > 12341 > 12314, we return "23141".

Constraints

3 <= 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.

Brute Force Enumeration

Intuition Try removing each occurrence of the digit and keep track of the maximum result.

Steps

• Iterate through all positions in the string
• When we find the target digit, create a new string by removing that character
• Compare the new string with the current maximum and update if larger
• Return the maximum result found

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        max_result = ""
        for i, c in enumerate(number):
            if c == digit:
                new_num = number[:i] + number[i+1:]
                if new_num > max_result:
                    max_result = new_num
        return max_result

Complexity

• Time: O(n²) where n is the length of the string (string concatenation takes O(n))
• Space: O(n) for storing the result strings
• Notes: Simple to understand but not optimal due to string concatenation overhead

Greedy Approach

Intuition To maximize the result, we should remove the first occurrence of the digit that is followed by a larger digit. If no such position exists, remove the last occurrence.

Steps

• Iterate through the string (except the last character)
• If we find the target digit followed by a larger digit, remove this occurrence and return
• If no such position is found, remove the last occurrence of the digit

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        for i in range(len(number) - 1):
            if number[i] == digit and number[i + 1] > digit:
                return number[:i] + number[i+1:]
        # If no such position found, remove the last occurrence
        last_pos = number.rfind(digit)
        return number[:last_pos] + number[last_pos+1:]

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the result string
• Notes: Optimal solution with single pass through the string