Maximum Difference by Remapping a Digit

EASY

Description

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 <= 10⁸

Approaches

Checkout 2 different approaches to solve Maximum Difference by Remapping a Digit. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Maximum Difference by Remapping a Digit. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Maximum Difference by Remapping a Digit

Patterns:

MathGreedy