Remove Digit From Number to Maximize Result

Easy

#2057Time: O(N^2), where N is the length of the `number` string. The main loop runs N times. Inside the loop, creating a substring takes O(N) time, and string comparison also takes O(N) time, leading to a total of O(N * N) = O(N^2).Space: O(N), where N is the length of the `number` string. This space is used to store the temporary strings created in each iteration and the final result string.

Patterns

Greedy Enumeration

Data structures

String

Prompt

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 <= 100
number consists of digits from '1' to '9'.
digit is a digit from '1' to '9'.
digit occurs at least once in number.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating every possible outcome by removing each occurrence of the specified digit and then comparing these outcomes to find the maximum. We iterate through the input string number. For each character that matches the given digit, we form a new string by removing that character. We then compare this new string with the best result found so far and update it if the new one is larger.

Algorithm

Initialize a string variable maxResult to an empty string to store the lexicographically largest number string found so far.
Iterate through the input number string using an index i from 0 to number.length() - 1.
At each index i, check if the character number.charAt(i) is equal to the target digit.
If it is, construct a new temporary string temp by removing the character at index i. This can be done by concatenating the substring before i and the substring after i: number.substring(0, i) + number.substring(i + 1).
Compare the temp string with maxResult. Since we are dealing with numbers of the same length (N-1), a standard lexicographical string comparison works. If temp is greater than maxResult, update maxResult to temp.
After the loop finishes, maxResult will hold the desired result. Return maxResult.

Walkthrough

The core idea is to simulate the removal of each occurrence of digit one by one. We initialize a variable, say maxResult, to an empty string to keep track of the maximum number string found. We loop through the input string number from left to right. Inside the loop, if the character at the current position i is the digit we need to remove, we construct a new candidate string by taking the part of the string before i and the part after i and concatenating them. We then perform a lexicographical comparison between this new candidate string and our current maxResult. If the candidate string is greater, we update maxResult. After the loop has checked all characters, maxResult will hold the string representing the largest possible number. String comparison is suitable here as all resulting numbers will have the same length, and it correctly handles large numbers that might overflow standard integer types.

1class Solution {2    public String removeDigit(String number, char digit) {3        String maxResult = "";4        for (int i = 0; i < number.length(); i++) {5            if (number.charAt(i) == digit) {6                // Form the new string by removing the character at index i7                String temp = number.substring(0, i) + number.substring(i + 1);8                // Compare with the max result found so far9                if (maxResult.isEmpty() || temp.compareTo(maxResult) > 0) {10                    maxResult = temp;11                }12            }13        }14        return maxResult;15    }16}

Complexity

Time

O(N^2), where N is the length of the `number` string. The main loop runs N times. Inside the loop, creating a substring takes O(N) time, and string comparison also takes O(N) time, leading to a total of O(N * N) = O(N^2).

Space

O(N), where N is the length of the `number` string. This space is used to store the temporary strings created in each iteration and the final result string.

Trade-offs

Pros

The logic is straightforward and easy to understand.
It is guaranteed to be correct because it exhaustively checks every possible removal.

Cons

This approach is less efficient because it involves creating new string objects and performing string comparisons inside a loop.
The time complexity is quadratic, which can be slow for very long input strings (though the constraints keep it feasible).

A more efficient approach is to use a greedy strategy. To maximize the resulting number, we want the digits in the most significant positions (left side) to be as large as possible. We can achieve this by finding the first occurrence of digit from the left which is followed by a larger digit. Removing this digit will promote the larger digit to an earlier position, maximizing the number. If no such occurrence exists, it means removing any digit will not result in a "promotion" of a larger digit. In this case, to minimize the impact on the number's value, we should remove the rightmost occurrence of digit.

Algorithm

Initialize a variable lastOccurrenceIndex to -1. This will track the index of the last occurrence of digit.
Iterate through the number string with an index i from 0 to number.length() - 1.
If number.charAt(i) is the target digit:
- Check if this is not the last character of the string (i < number.length() - 1) and if the next character number.charAt(i + 1) is greater than digit.
- If this condition is true, we have found the optimal character to remove. The resulting number will be maximized by promoting the larger subsequent digit. Construct the result string by removing the character at i and return it immediately.
- If the condition is false, simply update lastOccurrenceIndex = i to remember the position of this digit.
If the loop completes without returning, it means no digit was followed by a larger digit. In this case, the best strategy is to remove the last occurrence of digit to have the minimal impact on the number's magnitude. The index for this is stored in lastOccurrenceIndex. Construct the string by removing the character at lastOccurrenceIndex and return it.

Walkthrough

The logic is based on a simple observation: to make a number larger, you should try to increase its most significant digits. We can iterate through the string number from left to right, looking for an index i where number.charAt(i) is our target digit and the next character number.charAt(i+1) is strictly greater than digit. If we find such an index i, this is the best character to remove. Removing number.charAt(i) replaces it with a larger digit number.charAt(i+1), guaranteeing a larger resulting number. Since we scan from the left, the first time we find this condition is at the most significant position possible, making it the optimal move. We can immediately build the result and return.

If we iterate through the whole string and never find such a condition, it implies that for every occurrence of digit, the following digit is smaller or equal. In this case, to maximize the number, we should preserve the most significant digits. This is achieved by removing the last occurrence of digit, as this has the least impact on the number's overall value. This entire logic can be implemented in a single pass.

1class Solution {2    public String removeDigit(String number, char digit) {3        int lastOccurrenceIndex = -1;4        for (int i = 0; i < number.length(); i++) {5            if (number.charAt(i) == digit) {6                // Greedily check if the next digit is larger7                if (i < number.length() - 1 && number.charAt(i + 1) > digit) {8                    // This is the optimal digit to remove.9                    // By removing it, we replace it with a larger digit.10                    // Since we iterate from left, this is the most significant11                    // position where such an improvement can be made.12                    return number.substring(0, i) + number.substring(i + 1);13                }14                // Keep track of the last occurrence of the digit15                lastOccurrenceIndex = i;16            }17        }18        // If the loop completes, remove the last occurrence.19        return number.substring(0, lastOccurrenceIndex) + number.substring(lastOccurrenceIndex + 1);20    }21}

Complexity

Time

O(N), where N is the length of the `number` string. We iterate through the string at most once. The final substring operation also takes O(N) time.

Space

O(N) for storing the resulting string. The auxiliary space complexity (excluding the output) is O(1).

Trade-offs

Pros

Highly efficient with a single pass over the string.
Optimal time complexity for this problem.
Minimal space usage.

Cons

The greedy logic is slightly more complex to reason about compared to the brute-force approach.

Solutions

Solution

1class Solution:2    def removeDigit(self, number: str, digit: str) -> str: return max(3        number[: i] + number[i + 1:] for i, d in enumerate(number) if d == digit)

1class Solution {2public3  String removeDigit(String number, char digit) {4    String ans = "0";5    for (int i = 0, n = number.length(); i < n; ++i) {6      char d = number.charAt(i);7      if (d == digit) {8        String t = number.substring(0, i) + number.substring(i + 1);9        if (ans.compareTo(t) < 0) {10          ans = t;11        }12      }13    }14    return ans;15  }16}

1class Solution {2public:3  string removeDigit(string number, char digit) {4    string ans = "0";5    for (int i = 0, n = number.size(); i < n; ++i) {6      char d = number[i];7      if (d == digit) {8        string t = number.substr(0, i) + number.substr(i + 1, n - i);9        if (ans < t) {10          ans = t;11        }12      }13    }14    return ans;15  }16};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem