Remove Digit From Number to Maximize Result — Solution
Remove Digit From Number to Maximize Result solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Remove Digit From Number to Maximize Result is an easy coding problem on strings, greedy and enumeration, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Strings, Greedy, Enumeration
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a positive integer as a string number and a single character digit that occurs in number at least once.
Remove exactly one occurrence of digit from number so that the remaining string, read as a decimal number, is as large as possible. Return that remaining string.
Example 1
Input: number = "1231", digit = "1"
Output: 231
Explanation: Removing the first `1` gives 231; removing the last gives 123.
Example 2
Input: number = "551", digit = "5"
Output: 51
Explanation: Either `5` gives the same result.
Example 3
Input: number = "9479", digit = "9"
Output: 947
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
Hints for Remove Digit From Number to Maximize Result
Hint 1
Every candidate has the same length, so comparing them as strings compares them as numbers.
Hint 2
Trying each occurrence and keeping the best already works for 100 digits.
Hint 3
Greedy: remove the first occurrence that is followed by a larger digit — that raises the earliest possible position. If no such occurrence exists, remove the last one.
How to solve Remove Digit From Number to Maximize Result
Removing digit at index i shifts the next character into position i. The result grows at the earliest position possible when that next character is larger than digit, so the best choice is the first such occurrence; if every occurrence is followed by a smaller-or-equal digit (or nothing), removing the last occurrence disturbs the number as late as possible.
Approach
- Scan
numberfrom left to right, remembering the indexlastof each occurrence ofdigit. - At an occurrence
iwithnumber[i+1] > digit, stop and remove indexi. - If the scan finishes, remove index
last. - Return the string without that character.
Why it works
Two candidates that remove occurrences i < j agree before position i; at position i the first has number[i+1] and the second still has digit. If number[i+1] > digit the first is larger, and choosing the earliest such i beats every later removal. If number[i+1] < digit the first is smaller, so a later removal wins; if they are equal the comparison moves on in the same way. Hence, without an improving occurrence, the last occurrence is best. The simple alternative — build all candidates and keep the largest — is also correct at these sizes.
Complexity
- Time —
O(n) - Space —
O(n) for the result
Pitfalls
- Do not convert to an integer: 100 digits overflow every fixed-width type.
- Removing the first occurrence is not always right (
"9479"with9). - With no improving occurrence, remove the last occurrence, not the first.
Reference solution
Python
def removeDigit(number: str, digit: str) -> str:
last = -1
for i, c in enumerate(number):
if c == digit:
last = i
if i + 1 < len(number) and number[i + 1] > digit:
break
return number[:last] + number[last + 1:]Java
public static String removeDigit(String number, String digit) {
char d = digit.charAt(0);
int idx = -1;
for (int i = 0; i < number.length(); i++) {
if (number.charAt(i) == d) {
idx = i;
if (i + 1 < number.length() && number.charAt(i + 1) > d) break;
}
}
return number.substring(0, idx) + number.substring(idx + 1);
}C++
string removeDigit(string number, string digit) {
char d = digit[0];
int n = number.size(), idx = -1;
for (int i = 0; i < n; i++) {
if (number[i] == d) {
idx = i;
if (i + 1 < n && number[i + 1] > d) break;
}
}
return number.substr(0, idx) + number.substr(idx + 1);
}JavaScript
var removeDigit = function(number, digit) {
var idx = -1;
for (var i = 0; i < number.length; i++) {
if (number[i] === digit) {
idx = i;
if (i + 1 < number.length && number[i + 1] > digit) break;
}
}
return number.slice(0, idx) + number.slice(idx + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms