# Maximum Difference by Remapping a Digit
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-difference-by-remapping-a-digit)
Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-by-remapping-a-digit
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
---
## Problem
You are given an integer `num`. You know that Bob will sneakily **remap** one of the `10` possible digits (`0` to `9`) to another digit.

Return _the difference between the maximum and minimum values Bob can make by remapping **exactly** **one** digit in_ `num`.

**Notes:**

* When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of `d1` in `num` with `d2`.
* Bob can remap a digit to itself, in which case `num` does not change.
* Bob can remap different digits for obtaining minimum and maximum values respectively.
* The resulting number after remapping can contain leading zeroes.

**Example 1:**

**Input:** num = 11891
**Output:** 99009
**Explanation:** 
To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.

**Example 2:**

**Input:** num = 90
**Output:** 99
**Explanation:**
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.

**Constraints:**

* `1 <= num <= 108`

# Approaches
## Brute-Force Simulation
This approach exhaustively tries every possible remapping. There are 10 digits to choose from (0-9) and 10 digits to remap to (0-9). We can iterate through all 100 possible pairs of (digit to replace, replacement digit), apply the remapping to the original number, and keep track of the minimum and maximum values encountered.
**Time:** O(C * L), where C is the number of possible remappings (10 * 10 = 100) and L is the number of digits in `num`. Since C is a constant, this simplifies to O(L), but with a large constant factor. · **Space:** O(L), where L is the number of digits in `num`. This space is used to store the string representation of the number and the temporary strings created in each iteration.
**Pros:** Simple to conceptualize and implement.; Guaranteed to be correct as it explores the entire search space of single-digit remappings.
**Cons:** Performs many redundant or unnecessary computations. For example, it tries remapping digits that are not present in the input number.; Less efficient due to a large constant factor (100) in its time complexity compared to a direct analytical approach.
### Explanation
The core idea is to simulate the process for all 100 possible remappings. We convert the number to a string to make digit replacement easier. We then use two nested loops: the outer loop selects the digit `d1` to be replaced (from '0' to '9'), and the inner loop selects the digit `d2` to replace it with (from '0' to '9'). In each iteration, we generate a new number by performing the replacement `s.replace(d1, d2)`. This new number is then compared with our running maximum and minimum values, which are updated accordingly. Finally, after checking all possibilities, the difference between the maximum and minimum gives the answer.
### Algorithm
- Convert the input number `num` to its string representation, `s`.
- Initialize `maxVal` and `minVal` to `num`.
- Iterate through all possible digits to be replaced, `d1`, from '0' to '9'.
- Inside this loop, iterate through all possible replacement digits, `d2`, from '0' to '9'.
- For each pair `(d1, d2)`, create a new string `temp_s` by replacing all occurrences of `d1` in `s` with `d2`.
- Convert `temp_s` to an integer `currentVal`.
- Update `maxVal = max(maxVal, currentVal)`.
- Update `minVal = min(minVal, currentVal)`.
- After the loops complete, return `maxVal - minVal`.

## Optimized Direct Calculation
Instead of checking all 100 possible remappings, we can analytically determine the single best remapping to achieve the maximum value and the single best remapping for the minimum value. This direct approach is significantly more efficient.
**Time:** O(L), where L is the number of digits in `num`. We perform a few passes over the string representation of the number, resulting in a linear time complexity. · **Space:** O(L), where L is the number of digits in `num`. Space is required for the string representations of the numbers.
**Pros:** Highly efficient with a minimal constant factor.; Avoids unnecessary computations by directly targeting the optimal remappings.
**Cons:** Requires careful logical deduction to ensure the strategies for finding the max and min values are correct for all edge cases.
### Explanation
This optimized approach is based on the principle that changes to more significant (leftmost) digits have a greater impact on the number's value.

**For the maximum value:** To make the number as large as possible, we should change a digit to '9'. To maximize the impact, we should modify the leftmost possible digit. Therefore, we find the first digit from the left that is not '9' and replace all of its occurrences with '9'. If all digits are already '9', the number cannot be increased.

**For the minimum value:** To make the number as small as possible, we should change a digit to '0'. Again, to maximize the impact (in this case, the decrease in value), we should target the most significant digit. By replacing all occurrences of the very first digit with '0', we achieve the largest possible reduction in value.

By directly calculating these two optimal values and finding their difference, we arrive at the solution much faster than the brute-force method.

```java
class Solution {
    public int maxDiff(int num) {
        String s = String.valueOf(num);
        
        // Calculate maxVal
        int maxVal = num;
        char replaceForMax = ' ';
        for (char c : s.toCharArray()) {
            if (c != '9') {
                replaceForMax = c;
                break;
            }
        }
        if (replaceForMax != ' ') {
            maxVal = Integer.parseInt(s.replace(replaceForMax, '9'));
        }
        
        // Calculate minVal
        char replaceForMin = s.charAt(0);
        int minVal = Integer.parseInt(s.replace(replaceForMin, '0'));
        
        return maxVal - minVal;
    }
}
```
### Algorithm
- Convert the input number `num` to its string representation, `s`.
- **To find the maximum value (`maxVal`):**
  - Find the first digit from the left, `x`, that is not '9'.
  - If no such digit exists (all digits are '9'), `maxVal` is simply `num`.
  - Otherwise, create a new string by replacing all occurrences of `x` in `s` with '9'.
  - Convert this new string to an integer to get `maxVal`.
- **To find the minimum value (`minVal`):**
  - Take the first digit of `s`, let it be `y`.
  - Create a new string by replacing all occurrences of `y` in `s` with '0'.
  - Convert this new string to an integer to get `minVal`.
- Return `maxVal - minVal`.

# Solutions
### Java

```java
class Solution {
public
  int minMaxDifference(int num) {
    String s = String.valueOf(num);
    int mi = Integer.parseInt(s.replace(s.charAt(0), '0'));
    for (char c : s.toCharArray()) {
      if (c != '9') {
        return Integer.parseInt(s.replace(c, '9')) - mi;
      }
    }
    return num - mi;
  }
}

```

### JavaScript

```javascript
/** * @param {number} num * @return {number} */ var minMaxDifference =
  function (num) {
    const s = num.toString();
    const mi = +s.replaceAll(s[0], " 0 ");
    for (const c of s) {
      if (c !== " 9 ") {
        const mx = +s.replaceAll(c, " 9 ");
        return mx - mi;
      }
    }
    return num - mi;
  };

```

### CPP

```cpp
class Solution {
public:
  int minMaxDifference(int num) {
    string s = to_string(num);
    string t = s;
    char first = s[0];
    for (char &c : s) {
      if (c == first) {
        c = '0';
      }
    }
    int mi = stoi(s);
    for (int i = 0; i < t.size(); ++i) {
      if (t[i] != '9') {
        char second = t[i];
        for (int j = i; j < t.size(); ++j) {
          if (t[j] == second) {
            t[j] = '9';
          }
        }
        return stoi(t) - mi;
      }
    }
    return num - mi;
  }
};

```

### Python

```python
class Solution:
    def minMaxDifference(self, num: int) -> int: s = str(num) mi = int(s . replace(s[0], '0')) for c in s: if c != '9': return int(s . replace(c, '9')) - mi return num - mi

```