Maximum Difference by Remapping a Digit

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.

Examples

Example 1

1
2
3
4
5
6


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

1
2
3
4
5


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^8

Solution

Method 1 – Greedy Digit Remapping

Intuition

To maximize the difference, remap a digit in num to 9 for the maximum value and to 0 for the minimum value. Try all possible digit remappings and pick the best results. Since only one digit can be remapped at a time (all its occurrences), brute-force all digit-to-digit remaps for both max and min.

Approach

Convert num to a string for easy digit manipulation.
For the maximum value:

For each digit d from 0 to 9, replace all occurrences of d with 9 and record the resulting integer.
Track the largest value obtained.

For the minimum value:

For each digit d from 0 to 9, replace all occurrences of d with 0 and record the resulting integer.
Track the smallest value obtained.

Return the difference between the maximum and minimum values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
   int minMaxDifference(int num) {
      string s = to_string(num);
      int mx = num, mn = num;
      for (char d = '0'; d <= '9'; ++d) {
        string t = s;
        for (char &c : t) if (c == d) c = '9';
        mx = max(mx, stoi(t));
      }
      for (char d = '0'; d <= '9'; ++d) {
        string t = s;
        for (char &c : t) if (c == d) c = '0';
        mn = min(mn, stoi(t));
      }
      return mx - mn;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func minMaxDifference(num int) int {
   s := fmt.Sprintf("%d", num)
   mx, mn := num, num
   for d := byte('0'); d <= '9'; d++ {
      t := []byte(s)
      for i := range t {
        if t[i] == d {
           t[i] = '9'
        }
      }
      v, _ := strconv.Atoi(string(t))
      if v > mx {
        mx = v
      }
   }
   for d := byte('0'); d <= '9'; d++ {
      t := []byte(s)
      for i := range t {
        if t[i] == d {
           t[i] = '0'
        }
      }
      v, _ := strconv.Atoi(string(t))
      if v < mn {
        mn = v
      }
   }
   return mx - mn
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
   public int minMaxDifference(int num) {
      String s = Integer.toString(num);
      int mx = num, mn = num;
      for (char d = '0'; d <= '9'; d++) {
        String t = s.replace(d, '9');
        mx = Math.max(mx, Integer.parseInt(t));
      }
      for (char d = '0'; d <= '9'; d++) {
        String t = s.replace(d, '0');
        mn = Math.min(mn, Integer.parseInt(t));
      }
      return mx - mn;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
   fun minMaxDifference(num: Int): Int {
      val s = num.toString()
      var mx = num
      var mn = num
      for (d in '0'..'9') {
        val t = s.replace(d, '9')
        mx = maxOf(mx, t.toInt())
      }
      for (d in '0'..'9') {
        val t = s.replace(d, '0')
        mn = minOf(mn, t.toInt())
      }
      return mx - mn
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
   def minMaxDifference(self, num: int) -> int:
      s = str(num)
      mx = num
      mn = num
      for d in '0123456789':
        t = s.replace(d, '9')
        mx = max(mx, int(t))
      for d in '0123456789':
        t = s.replace(d, '0')
        mn = min(mn, int(t))
      return mx - mn

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


impl Solution {
   pub fn min_max_difference(num: i32) -> i32 {
      let s = num.to_string();
      let mut mx = num;
      let mut mn = num;
      for d in b'0'..=b'9' {
        let t: String = s.bytes().map(|c| if c == d { b'9' } else { c }).map(|c| c as char).collect();
        let v = t.parse::<i32>().unwrap();
        if v > mx { mx = v; }
      }
      for d in b'0'..=b'9' {
        let t: String = s.bytes().map(|c| if c == d { b'0' } else { c }).map(|c| c as char).collect();
        let v = t.parse::<i32>().unwrap();
        if v < mn { mn = v; }
      }
      mx - mn
   }
}

Complexity

⏰ Time complexity: O(k*10), where k is the number of digits in num (since we try all 10 digits for both max and min).
🧺 Space complexity: O(k) for string manipulation.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy Digit Remapping#

Intuition#

Approach#

Code#

Complexity#