LeetCode 2259 - Remove Digit From Number to Maximize Result
The problem gives us a string called number, which represents a positive integer, and a character digit, which is guaranteed to appear at least once inside number.
Difficulty: 🟢 Easy
Topics: String, Greedy, Enumeration
Solution
LeetCode 2259 - Remove Digit From Number to Maximize Result
Problem Understanding
The problem gives us a string called number, which represents a positive integer, and a character digit, which is guaranteed to appear at least once inside number.
Our task is to remove exactly one occurrence of digit from the string so that the resulting number is as large as possible. The result must also be returned as a string.
Since the input is provided as a string instead of an integer, we should think in terms of string manipulation and lexicographical comparison. Because all characters are numeric digits and all candidate results have the same length after removal, lexicographical comparison works the same as numerical comparison.
For example, if:
number = "1231"
digit = "1"
we have two possible removals:
- Remove the first
'1'→"231" - Remove the second
'1'→"123"
Since "231" represents the larger number, the correct answer is "231".
The constraints are very small:
2 <= number.length <= 100- Digits are only from
'1'to'9' digitalways exists innumber
Because the string length is at most 100, even a brute-force solution is completely acceptable. However, the problem is designed to reward recognizing a greedy observation that allows us to choose the best removal efficiently.
Several edge cases are important:
- The target digit may appear only once.
- Multiple removals may produce the same result.
- The best removal may not be the first occurrence.
- The best removal may not be the last occurrence.
- Adjacent equal digits can create ties.
- Removing a digit near the front usually has a larger impact than removing one near the end.
Understanding how digit positions affect the final value is the key insight behind the optimal solution.
Approaches
Brute Force Approach
The most direct solution is to try removing every occurrence of digit.
For each index where number[i] == digit, we create a new string by skipping that character:
candidate = number[:i] + number[i+1:]
We then compare all generated candidates and keep the largest one.
This works because we explicitly evaluate every valid possibility. Since one of those possibilities must be optimal, taking the maximum guarantees the correct answer.
The time complexity is acceptable because the string length is at most 100. If there are n characters, we may generate up to n candidate strings, and each string construction costs O(n), giving total complexity O(n²).
Optimal Greedy Approach
The greedy insight comes from understanding how digit positions affect the resulting number.
When comparing two numbers of the same length, the earlier digits matter more than the later digits. Therefore, we want the left side of the number to become as large as possible as early as possible.
Suppose we are looking at an occurrence of digit at position i.
If the next digit, number[i + 1], is larger than digit, then removing the current occurrence is beneficial. Why?
Because removing the smaller digit allows the larger following digit to shift left into a more significant position.
For example:
number = "1231"
digit = "1"
At index 0:
1 2 3 1
^
The next digit is 2, which is larger than 1.
Removing this 1 gives:
231
which is larger than removing the later 1.
Therefore, the greedy rule is:
- Remove the first occurrence where the next digit is larger than
digit - If no such occurrence exists, remove the last occurrence of
digit
This works because delaying removal only helps when the following digits are not larger.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Generates every possible candidate string |
| Optimal | O(n) | O(n) | Uses greedy observation to choose removal immediately |
Algorithm Walkthrough
- Iterate through the string from left to right.
- Whenever the current character equals
digit, check the next character if it exists. - If the next character is larger than
digit, immediately remove the current occurrence and return the resulting string. - This removal is optimal because moving a larger digit into an earlier position increases the overall number as early as possible.
- If no occurrence satisfies this condition, continue scanning until the end.
- After the loop finishes, remove the last occurrence of
digit. - Return the final constructed string.
Why it works
The algorithm relies on positional significance in decimal numbers. Earlier digits contribute more to the value than later digits. If removing a digit allows a larger digit to move left earlier, that choice dominates all later possibilities.
If no occurrence has a larger next digit, then removing earlier occurrences would expose digits that are smaller or equal, which cannot improve the result. In that case, keeping the left side unchanged as long as possible is best, so we remove the last occurrence.
Python Solution
class Solution:
def removeDigit(self, number: str, digit: str) -> str:
last_index = -1
for i in range(len(number)):
if number[i] == digit:
last_index = i
if i + 1 < len(number) and number[i + 1] > digit:
return number[:i] + number[i + 1:]
return number[:last_index] + number[last_index + 1:]
The implementation starts by tracking the last occurrence of digit. This is necessary because if no greedy removal condition is found, we must remove the last occurrence.
During iteration, every time we encounter digit, we update last_index.
The critical greedy condition is:
number[i + 1] > digit
If the next digit is larger, we immediately remove the current digit and return the result. This early return works because the first such occurrence is always optimal.
If the loop completes without finding a beneficial removal point, the algorithm removes the last occurrence using the stored index.
String slicing creates the new result efficiently and keeps the implementation concise.
Go Solution
func removeDigit(number string, digit byte) string {
lastIndex := -1
for i := 0; i < len(number); i++ {
if number[i] == digit {
lastIndex = i
if i+1 < len(number) && number[i+1] > digit {
return number[:i] + number[i+1:]
}
}
}
return number[:lastIndex] + number[lastIndex+1:]
}
The Go implementation follows the same greedy logic as the Python solution.
One important difference is that Go strings are indexed using bytes. Since the input contains only ASCII digits, direct byte indexing is completely safe and efficient.
String slicing in Go works similarly to Python slicing, allowing us to construct the result by concatenating the substring before the removed character with the substring after it.
No integer conversion is necessary because character comparisons between digit bytes preserve numeric ordering.
Worked Examples
Example 1
number = "123"
digit = "3"
| Index | Character | Action |
|---|---|---|
| 0 | '1' | Not target digit |
| 1 | '2' | Not target digit |
| 2 | '3' | Store last occurrence |
No next character exists after index 2, so no greedy removal occurs.
Remove the last occurrence:
"12"
Final answer:
"12"
Example 2
number = "1231"
digit = "1"
| Index | Character | Next Character | Action |
|---|---|---|---|
| 0 | '1' | '2' | '2' > '1', remove current digit |
Construct result:
"231"
Final answer:
"231"
Example 3
number = "551"
digit = "5"
| Index | Character | Next Character | Action |
|---|---|---|---|
| 0 | '5' | '5' | Next digit not larger |
| 1 | '5' | '1' | Next digit not larger |
No greedy removal found.
Remove the last occurrence of '5':
"51"
Final answer:
"51"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We scan the string once |
| Space | O(n) | Result string creation requires linear space |
The algorithm performs a single pass through the input string, giving linear time complexity.
Although the algorithm itself uses only a few variables, strings are immutable in both Python and Go. Constructing the final result requires creating a new string of size n - 1, so the effective space complexity is O(n).
Test Cases
solution = Solution()
# Provided examples
assert solution.removeDigit("123", "3") == "12" # single occurrence
assert solution.removeDigit("1231", "1") == "231" # remove earlier occurrence
assert solution.removeDigit("551", "5") == "51" # equal results possible
# Remove first occurrence for maximum gain
assert solution.removeDigit("133235", "3") == "13235" # next digit larger
# Remove last occurrence when no better choice exists
assert solution.removeDigit("76555", "5") == "7655" # all following digits smaller/equal
# Multiple identical digits
assert solution.removeDigit("1111", "1") == "111" # any removal same
# Target digit appears once
assert solution.removeDigit("9876", "8") == "976" # forced removal
# Increasing sequence
assert solution.removeDigit("12345", "2") == "1345" # greedy removal
# Decreasing sequence
assert solution.removeDigit("54321", "3") == "5421" # remove only occurrence
# Best removal near middle
assert solution.removeDigit("15252", "5") == "1522" # remove later occurrence
# Adjacent target digits
assert solution.removeDigit("1001", "0") == "101" # choose optimal zero
# Minimum length input
assert solution.removeDigit("22", "2") == "2" # smallest valid size
Test Summary
| Test | Why |
|---|---|
"123", "3" |
Validates single occurrence handling |
"1231", "1" |
Confirms greedy removal of earlier digit |
"551", "5" |
Tests equal-result removals |
"133235", "3" |
Verifies first beneficial removal |
"76555", "5" |
Ensures fallback to last occurrence |
"1111", "1" |
Handles all identical digits |
"9876", "8" |
Tests single mandatory removal |
"12345", "2" |
Confirms increasing-order behavior |
"54321", "3" |
Confirms decreasing-order behavior |
"15252", "5" |
Tests multiple separated occurrences |
"1001", "0" |
Handles repeated zero-like structure |
"22", "2" |
Tests minimum input size |
Edge Cases
One important edge case occurs when the target digit appears only once. In this situation, there is no decision to make because exactly one removal is possible. A buggy implementation might still attempt greedy comparisons beyond bounds or incorrectly track multiple candidates. The current implementation handles this naturally because the loop stores the only occurrence and removes it at the end if no earlier return happens.
Another critical edge case is when all occurrences of the digit produce the same result. For example:
number = "551"
digit = "5"
Removing either '5' produces "51". Some implementations may unnecessarily overcomplicate tie handling. The greedy approach works correctly because removing the last occurrence still yields the optimal result.
A third important case is when the best removal is near the front of the string. Earlier positions have greater positional value, so removing a digit that exposes a larger following digit can dramatically increase the number. For example:
"1231", digit = "1"
Removing the first '1' produces "231", which is much larger than "123". The implementation explicitly checks for this condition and immediately returns once found.
Another subtle edge case occurs when adjacent digits are equal to the target digit. For example:
number = "1111"
digit = "1"
Every removal yields the same result. The algorithm correctly scans through all occurrences and removes the final one after finding no beneficial position.