Code Implementation

class Solution:
    def maxDiff(self, num: int) -> int:
        s = list(str(num))
        # Find first digit that is not '9' for max
        for d in s:
            if d != '9':
                max_num = int(''.join(['9' if x == d else x for x in s]))
                break
        else:
            max_num = num
        # Find first digit that is not '1' for min (first digit), else not '0' for others
        if s[0] != '1':
            d = s[0]
            min_num = int(''.join(['1' if x == d else x for x in s]))
        else:
            for d in s[1:]:
                if d != '0' and d != '1':
                    min_num = int(''.join([x if x != d else '0' for x in s]))
                    break
            else:
                min_num = num
        return max_num - min_num
      

class Solution {
public:
    int maxDiff(int num) {
        string s = to_string(num);
        string max_s = s, min_s = s;
        // Maximize: replace first non-9 digit with 9
        for (char d : s) {
            if (d != '9') {
                for (char &c : max_s) {
                    if (c == d) c = '9';
                }
                break;
            }
        }
        // Minimize: replace first digit != 1 (if first), else next digit != 0/1 with 0
        if (s[0] != '1') {
            char d = s[0];
            for (char &c : min_s) {
                if (c == d) c = '1';
            }
        } else {
            for (int i = 1; i < s.size(); ++i) {
                if (s[i] != '0' && s[i] != '1') {
                    char d = s[i];
                    for (int j = 0; j < min_s.size(); ++j) {
                        if (min_s[j] == d) min_s[j] = '0';
                    }
                    break;
                }
            }
        }
        return stoi(max_s) - stoi(min_s);
    }
};
      

class Solution {
    public int maxDiff(int num) {
        String s = Integer.toString(num);
        char[] maxArr = s.toCharArray();
        char[] minArr = s.toCharArray();
        // Maximize: replace first non-9 digit with 9
        for (char d : maxArr) {
            if (d != '9') {
                for (int i = 0; i < maxArr.length; ++i) {
                    if (maxArr[i] == d) maxArr[i] = '9';
                }
                break;
            }
        }
        // Minimize: replace first digit != 1 (if first), else next digit != 0/1 with 0
        if (minArr[0] != '1') {
            char d = minArr[0];
            for (int i = 0; i < minArr.length; ++i) {
                if (minArr[i] == d) minArr[i] = '1';
            }
        } else {
            for (int i = 1; i < minArr.length; ++i) {
                if (minArr[i] != '0' && minArr[i] != '1') {
                    char d = minArr[i];
                    for (int j = 0; j < minArr.length; ++j) {
                        if (minArr[j] == d) minArr[j] = '0';
                    }
                    break;
                }
            }
        }
        int maxNum = Integer.parseInt(new String(maxArr));
        int minNum = Integer.parseInt(new String(minArr));
        return maxNum - minNum;
    }
}
      

var maxDiff = function(num) {
    let s = num.toString().split('');
    let maxNum = num, minNum = num;
    // Maximize: replace first non-9 digit with 9
    for (let d of s) {
        if (d !== '9') {
            maxNum = parseInt(s.map(x => x === d ? '9' : x).join(''));
            break;
        }
    }
    // Minimize: replace first digit != 1 (if first), else next digit != 0/1 with 0
    if (s[0] !== '1') {
        let d = s[0];
        minNum = parseInt(s.map(x => x === d ? '1' : x).join(''));
    } else {
        for (let i = 1; i < s.length; ++i) {
            if (s[i] !== '0' && s[i] !== '1') {
                let d = s[i];
                minNum = parseInt(s.map(x => x === d ? '0' : x).join(''));
                break;
            }
        }
    }
    return maxNum - minNum;
};
      

Problem Description

Given an integer num, you are allowed to perform the following operation exactly once: pick a single digit (0-9) and replace all occurrences of that digit in num with any other digit (0-9). You must perform this operation twice: once to maximize the resulting integer, and once to minimize it (note: the number cannot have leading zeros after the operation).
Your task is to compute and return the maximum difference between the largest and smallest values you can obtain by this process.
Constraints:

• The integer num is positive (no negative numbers or zero).
• You must perform the digit replacement exactly once for each case (max and min).
• Leading zeros are not allowed in the result.

Thought Process

At first glance, it might seem that we need to try all possible digit replacements for both maximizing and minimizing the number. For each digit (0-9), we could try replacing it with every other digit (also 0-9), and compute the resulting numbers, taking care to avoid leading zeros.
However, this brute-force approach would be inefficient, especially for numbers with many digits. Instead, we can reason about the optimal way to maximize and minimize the number:

• To maximize the number, we want to replace a digit with '9' (the largest possible digit) wherever possible.
• To minimize the number, we want to replace a digit with '1' or '0' (the smallest possible digits), but we must avoid leading zeros.

Solution Approach

Here’s how we can systematically solve the problem:

1. Convert the number to a string or array of digits.
   This allows us to easily access and replace digits.
2. Maximizing the number:
   • Find the first digit (from left) that is not already '9'.
   • Replace all occurrences of this digit with '9'.
   • If all digits are already '9', the number is already maximized.
3. Minimizing the number:
   • If the first digit is not '1', replace all its occurrences with '1' (since '0' would create an invalid leading zero).
   • If the first digit is '1', look for the first digit (from the second position onwards) that is not '0' or '1'. Replace all its occurrences with '0'.
   • If all digits are '0' or '1', the number is already minimized.
4. Compute the difference:
   Subtract the minimized number from the maximized number.

Example Walkthrough

Let's walk through an example with num = 555:

• Maximizing:
  • The first digit not '9' is '5'.
  • Replace all '5's with '9' ⇒ 999.
• Minimizing:
  • The first digit is '5', which is not '1'.
  • Replace all '5's with '1' ⇒ 111.
• Difference: 999 - 111 = 888.

• Maximizing:
  • The first digit not '9' is '2' (at position 1).
  • Replace all '2's with '9' ⇒ 9988.
• Minimizing:
  • The first digit is '9', which is not '1'.
  • Replace all '9's with '1' ⇒ 1288.
• Difference: 9988 - 1288 = 8700.

Time and Space Complexity

Brute-force approach:

• For each digit (0-9), try replacing it with every other digit (0-9), for both maximizing and minimizing. For an n-digit number, this is O(10 * 9 * n) for each case.

• We only scan the number a few times (to find the digit to replace, and to perform the replacements), each of which is O(n), where n is the number of digits.
• Space complexity is O(n) due to storing the string/array representation of the number.

Summary

The key insight is to realize that for maximizing, we should replace the first non-'9' digit with '9', and for minimizing, the first digit (if not '1') with '1', or the first non-'0'/'1' digit (after the first) with '0'. This approach avoids brute-force enumeration and ensures optimal results by leveraging the structure of decimal numbers. The solution is efficient, elegant, and easy to implement in any language.