Watch 10 video solutions for Remove Digit From Number to Maximize Result, a easy level problem involving String, Greedy, Enumeration. This walkthrough by Coding Decoded has 4,166 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |