{x}
blog image

Remove Digit From Number to Maximize Result

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.

Solution Explanation:

The problem asks to remove exactly one occurrence of a given digit from a number string to maximize the resulting numerical value. Two approaches are presented: brute force and greedy.

Approach 1: Brute Force Enumeration

This approach iterates through each digit in the input string number. If a digit matches the target digit, it removes that digit and creates a new string. It keeps track of the maximum value obtained among all such removals.

Algorithm:

  1. Iterate: Loop through each index i of the number string.
  2. Check: If number[i] is equal to digit, remove number[i] by concatenating the substrings before and after i.
  3. Update Maximum: Compare the newly created string (converted to an integer for comparison) with the current maximum value. If it's larger, update the maximum.
  4. Return: After iterating through all digits, return the string representation of the maximum value found.

Time Complexity: O(n^2), where n is the length of the number string. This is because string concatenation in the loop takes O(n) time in the worst case.

Space Complexity: O(n) in the worst case, to store the resulting strings.

Approach 2: Greedy

This approach is more efficient. It recognizes that to maximize the resulting number, we should prioritize removing digits that are smaller than their subsequent digits.

Algorithm:

  1. Iterate: Loop through each index i of the number string.
  2. Check: If number[i] is equal to digit:
    • If i + 1 is within bounds and number[i] < number[i+1], this means removing number[i] will yield a larger value. Remove number[i] and return the resulting string. This is because removing a smaller digit before a larger one will always give a bigger result.
  3. Last Occurrence: If no such digit is found during the iteration, it means that removing any occurrence of the digit will yield the same result. In this case, we remove the last occurrence of the digit.

Time Complexity: O(n), where n is the length of the number string. We iterate through the string only once.

Space Complexity: O(1). We use constant extra space.

Code in Different Languages:

The code examples for both approaches are provided in the problem statement. Note that the greedy approach is significantly more efficient than the brute force approach, especially for larger input strings. Therefore, the greedy approach is preferred.