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 <= 100number consists of digits from '1' to '9'.digit is a digit from '1' to '9'.digit occurs at least once in number.Problem Overview: You receive a numeric string number and a digit digit. Remove exactly one occurrence of that digit so the resulting string represents the largest possible number. The challenge is choosing which occurrence to remove without converting the entire value to integers or performing unnecessary comparisons.
Approach 1: Brute Force Enumeration (O(n²) time, O(n) space)
Scan the string and try removing every occurrence of digit. For each candidate index, build a new string by concatenating the prefix and suffix around that position. Compare the generated numbers lexicographically and keep the largest one. This works because all candidates have the same length after removal, so string comparison correctly reflects numeric order. The approach is simple and demonstrates the problem clearly, but constructing up to n strings of length n leads to O(n²) time. This method mainly serves as a baseline when reasoning about enumeration strategies.
Approach 2: Greedy Approach - Remove Digit for Maximum Number (O(n) time, O(1) space)
The optimal solution relies on a greedy observation. If a digit equal to digit is followed by a larger digit, removing it immediately increases the number because the larger digit shifts to a more significant position. Iterate through the string and look for the first index i where number[i] == digit and number[i+1] > number[i]. Remove that digit and return the result. If no such position exists, the number is non-increasing around that digit, so removing the last occurrence of digit yields the maximum value.
This greedy rule works because earlier digits contribute more to the numeric value. Eliminating a smaller digit before a larger neighbor maximizes the prefix as early as possible. The scan happens once, giving O(n) time and constant extra space. The logic fits well with common patterns in greedy algorithms and string processing where local optimal choices produce the global optimum.
Recommended for interviews: Interviewers expect the greedy observation. Starting with brute force shows you understand the search space, but recognizing the "remove before a larger next digit" rule demonstrates algorithmic intuition and reduces the complexity from O(n²) to O(n). The implementation is short, readable, and avoids unnecessary string comparisons.
Iterate through the string and check each occurrence of the given digit. For each occurrence, remove it to form a new number. Compare each of these new numbers and return the largest one.
This Python solution iterates over each character in the string 'number'. When it finds the specified 'digit', it creates a new string by excluding that particular digit from 'number'. Each new string is compared to the previously recorded maximum value. After the loop, the maximum string found is returned.
Time Complexity: O(n), where n is the length of 'number'.
Space Complexity: O(1), as only a few variables are used regardless of the input size.
We can enumerate all positions i in the string number. If number[i] = digit, we take the prefix number[0:i] and the suffix number[i+1:] of number and concatenate them. This gives the result after removing number[i]. We then take the maximum of all possible results.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string number.
We can enumerate all positions i in the string number. If number[i] = digit, we record the last occurrence position of digit as last. If i + 1 < n and number[i] < number[i + 1], then we can directly return number[0:i] + number[i+1:] as the result after removing number[i]. This is because if number[i] < number[i + 1], removing number[i] will result in a larger number.
After the traversal, we return number[0:last] + number[last+1:].
| Approach | Complexity |
|---|---|
| Greedy Approach - Remove Digit for Maximum Number | Time Complexity: O(n), where n is the length of 'number'. |
| Brute Force Enumeration | — |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(n) | When first analyzing the problem or validating all possibilities during reasoning |
| Greedy Removal Based on Next Digit | O(n) | O(1) | Optimal solution for interviews and production code |
Remove Digit From Number to Maximize Result | Leetcode 2259 | Syring | Contest 291 🔥🔥 • Coding Decoded • 4,166 views views
Watch 9 more video solutions →Practice Remove Digit From Number to Maximize Result with our built-in code editor and test cases.
Practice on FleetCode