# Remove Digit From Number to Maximize Result
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-digit-from-number-to-maximize-result)
Canonical: https://scaleengineer.com/dsa/problems/remove-digit-from-number-to-maximize-result
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## 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 <= 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
## Brute Force Iteration
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.
**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.
**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).
### Explanation
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.

```java
class Solution {
    public String removeDigit(String number, char digit) {
        String maxResult = "";
        for (int i = 0; i < number.length(); i++) {
            if (number.charAt(i) == digit) {
                // Form the new string by removing the character at index i
                String temp = number.substring(0, i) + number.substring(i + 1);
                // Compare with the max result found so far
                if (maxResult.isEmpty() || temp.compareTo(maxResult) > 0) {
                    maxResult = temp;
                }
            }
        }
        return maxResult;
    }
}
```
### 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`.

## Single-Pass Greedy Approach
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`.
**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).
**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.
### Explanation
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.

```java
class Solution {
    public String removeDigit(String number, char digit) {
        int lastOccurrenceIndex = -1;
        for (int i = 0; i < number.length(); i++) {
            if (number.charAt(i) == digit) {
                // Greedily check if the next digit is larger
                if (i < number.length() - 1 && number.charAt(i + 1) > digit) {
                    // This is the optimal digit to remove.
                    // By removing it, we replace it with a larger digit.
                    // Since we iterate from left, this is the most significant
                    // position where such an improvement can be made.
                    return number.substring(0, i) + number.substring(i + 1);
                }
                // Keep track of the last occurrence of the digit
                lastOccurrenceIndex = i;
            }
        }
        // If the loop completes, remove the last occurrence.
        return number.substring(0, lastOccurrenceIndex) + number.substring(lastOccurrenceIndex + 1);
    }
}
```
### 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.

# Solutions
### Python

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

```

### Java

```java
class Solution {
public
  String removeDigit(String number, char digit) {
    String ans = "0";
    for (int i = 0, n = number.length(); i < n; ++i) {
      char d = number.charAt(i);
      if (d == digit) {
        String t = number.substring(0, i) + number.substring(i + 1);
        if (ans.compareTo(t) < 0) {
          ans = t;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string removeDigit(string number, char digit) {
    string ans = "0";
    for (int i = 0, n = number.size(); i < n; ++i) {
      char d = number[i];
      if (d == digit) {
        string t = number.substr(0, i) + number.substr(i + 1, n - i);
        if (ans < t) {
          ans = t;
        }
      }
    }
    return ans;
  }
};

```