Remove Digit From Number to Maximize Result solution and explanation
Infosys
Google
9 more videos on this problem
Remove Digit From Number to Maximize Result | Leetcode 2259 | Syring | Contest 291 🔥🔥Coding Decoded · 5:57 · 4K views
Leetcode Weekly-contest-291 - Remove Digit From Number to Maximize ResultPrakhar Agrawal · 4:39 · 1K views
2259. Remove Digit From Number to Maximize Result (Leetcode Easy)Programming Live with Larry · 3:11 · 1K views
Leetcode 2259 Remove Digit From Number to Maximize Result (Java) - Leetcode Contest 291TheAnalyticGuy · 5:36 · 938 views
2259 Remove Digit From Number to Maximize Result| Leetcode Weekly Contest 291 | Leetcode 2259Ashutosh sharma · 6:56 · 913 views
Remove Digit From Number to Maximize Result - LeetCode 2259 - Java Solutionalgobest - Computer Science · 4:21 · 300 views
Remove Digit From Number to Maximize Result || LeetCode Weekly Contest #291Coding Battle · 6:53 · 288 views
Remove Digit From Number to Maximize Result | Leetcode 2259 | Approach + Code with explanation.Pirai's Academy · 11:43 · 217 views
Day 462 - Teaching Kids Programming - Remove Digit From Number to Maximize ResultDoctor Lai · 12:08 · 156 views
LeetCode 2259 | Remove Digit From Number to Maximize Result | String | JavaSleepy Cracker · 9:14 · 145 views
The problem
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 <= 100numberconsists of digits from'1'to'9'.digitis a digit from'1'to'9'.digitoccurs at least once innumber.
Approach overview
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 1: Greedy Approach - Remove Digit for Maximum Number
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.
def removeDigit(number: str, digit: str) -> str:
max_number = ''
for i in range(len(number)):
if number[i] == digit:
new_number = number[:i] + number[i+1:]
if new_number > max_number:
max_number = new_number
return max_numberpublic class Solution {
public String removeDigit(String number, char digit) {
String maxNumber = "";
for (int i = 0; i < number.length(); i++) {
if (number.charAt(i) == digit) {
String newNumber = number.substring(0, i) + number.substring(i + 1);
if (newNumber.compareTo(maxNumber) > 0) {
maxNumber = newNumber;
}
}
}
return maxNumber;
}
}#include <string>
#include <algorithm>
std::string removeDigit(std::string number, char digit) {
std::string max_number = "";
for (size_t i = 0; i < number.size(); ++i) {
if (number[i] == digit) {
std::string new_number = number.substr(0, i) + number.substr(i+1);
max_number = std::max(max_number, new_number);
}
}
return max_number;
}function removeDigit(number, digit) {
let maxNumber = '';
for (let i = 0; i < number.length; i++) {
if (number[i] === digit) {
let newNumber = number.slice(0, i) + number.slice(i + 1);
if (newNumber > maxNumber) {
maxNumber = newNumber;
}
}
}
return maxNumber;
}#include <stdio.h>
#include <string.h>
void removeDigit(const char* number, char digit, char* result) {
char max_number[101] = "";
for (size_t i = 0; i < strlen(number); ++i) {
if (number[i] == digit) {
strncpy(result, number, i);
strcpy(result + i, number + i + 1);
if (strcmp(result, max_number) > 0) {
strcpy(max_number, result);
}
}
}
strcpy(result, max_number);
}public class Solution {
public string RemoveDigit(string number, char digit) {
string maxNumber = "";
for (int i = 0; i < number.Length; i++) {
if (number[i] == digit) {
string newNumber = number.Substring(0, i) + number.Substring(i + 1);
if (String.Compare(newNumber, maxNumber) > 0) {
maxNumber = newNumber;
}
}
}
return maxNumber;
}
}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.
Approach 2: Brute Force Enumeration
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.
function removeDigit(number: string, digit: string): string {
const n = number.length;
let last = -1;
for (let i = 0; i < n; ++i) {
if (number[i] === digit) {
last = i;
if (i + 1 < n && number[i] < number[i + 1]) {
break;
}
}
}
return number.substring(0, last) + number.substring(last + 1);
}func removeDigit(number string, digit byte) string {
ans := "0"
for i, d := range number {
if d == rune(digit) {
t := number[:i] + number[i+1:]
if strings.Compare(ans, t) < 0 {
ans = t
}
}
}
return ans
}class Solution {
/**
* @param String $number
* @param String $digit
* @return String
*/
function removeDigit($number, $digit) {
$max = 0;
for ($i = 0; $i < strlen($number); $i++) {
if ($number[$i] == $digit) {
$tmp = substr($number, 0, $i) . substr($number, $i + 1);
if ($tmp > $max) {
$max = $tmp;
}
}
}
return $max;
}
}Approach 3: Greedy
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:].
func removeDigit(number string, digit byte) string {
last := -1
n := len(number)
for i := range number {
if number[i] == digit {
last = i
if i+1 < n && number[i] < number[i+1] {
break
}
}
}
return number[:last] + number[last+1:]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach - Remove Digit for Maximum Number | Time Complexity: O(n), where n is the length of 'number'. |
| Brute Force Enumeration | – |
| Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Remove Digit From Number to Maximize Result easy or hard?
The problem is classified as Easy on LeetCode. The main challenge is recognizing the greedy insight that removing a digit before a larger neighbor increases the final number. Once that observation is made, the implementation becomes straightforward.
Remove Digit From Number to Maximize Result Python/Java solution
In both Python and Java, the greedy solution scans the string and removes the first occurrence of the digit whose next digit is larger. If such a position is not found, remove the last occurrence. The implementation typically uses substring operations or slicing and runs in O(n) time.
How to solve Remove Digit From Number to Maximize Result in O(n)?
Iterate through the number string and check every position where the digit matches the target digit. If the next digit is greater than the current digit, remove that occurrence immediately and return the result. This greedy choice maximizes the number as early as possible. If no such position exists, remove the last occurrence of the digit.
What is the best approach for Remove Digit From Number to Maximize Result?
The greedy approach is the best solution. Scan the string and remove the first occurrence of the target digit where the next digit is larger. This increases the value because the larger digit shifts to a more significant position. If such a case does not exist, remove the last occurrence of the digit. The algorithm runs in O(n) time and O(1) space.
Is Remove Digit From Number to Maximize Result asked at Google/Amazon/Meta?
Problems involving greedy digit manipulation and string-based number optimization appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include removing digits to maximize or minimize a number and monotonic stack style greedy decisions.
What data structure is used in Remove Digit From Number to Maximize Result?
The problem mainly uses string traversal and greedy decision making. No complex data structures are required. The solution simply iterates through the string and constructs the resulting string after removing the selected digit.
What is the time complexity of Remove Digit From Number to Maximize Result?
The optimal greedy solution runs in O(n) time because the string is scanned once to find the best digit to remove. Space complexity is O(1) if the result is constructed directly from the original string. A brute force enumeration approach would take O(n²) time since it generates and compares multiple candidate strings.