Problem Statement

You are given an integer num. You will apply the following steps to num two separate times:

Pick a digit x (0 <= x <= 9).
Pick another digit y (0 <= y <= 9). Note y can be equal to x.
Replace all the occurrences of x in the decimal representation of num by y.
Let a and b be the two results from applying the operation to num independently.

Return the max difference between a and b.

Note that neither a nor b may have any leading zeros, and must not be 0.

Test Cases

Example 1:

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.
The second time pick x = 5 and y = 1 and store the new integer in b.
We have now a = 999 and b = 111 and max difference = 888
Example 2:

Input: num = 9
Output: 8
Explanation: The first time pick x = 9 and y = 9 and store the new integer in a.
The second time pick x = 9 and y = 1 and store the new integer in b.
We have now a = 9 and b = 1 and max difference = 8

Constraints:

1 <= num <= 10^8

Intuition

We care about the maximum value that we can get by replacing some digit with x and minimum value that we can get by replacing some digit with y.
This will always gives a maximum different.
To get the maximum value, we can replace the first digit which is not 9 with 9. This will give us the max value as 9.
Eg :
92321 => replacing 2 with 9 => 99391

Similarly we need to get the minimum value. Incase of minimum value, there are two cases to consider.

• If the first number is > 1, in that case, we can replace it with 1 and it will give us the minimum. Eg : 92321 => replace 9 by 1 => 12321. We can replace by 0, as no leading zero is allowed.
• Another case if first number is already 1. If it is already 1, then we need to find the number > 1 and replace it with 0. Eg : 11112 => replace last 2 by 0 => 11110

Difference between them will give us the result.

Approach

• Convert the number to string for easy processing.
• Find the first digit which is not 9 and convert all its occurance to 9. This is our max.
• Find the digit which is either > 1, replace it 1 or if its already 1, replace with 0.
• Parse it to get the intervalue and take the different.

Complexity

• Time complexity:

  O(10) as we are going through the digit, as there can be only 10 digit max.

• Space complexity:

  O(10) as we are creating strings.

Code

class Solution {
    public int maxDiff(int num) {
        char [] forMax = Integer.toString(num).toCharArray();
        char [] forMin = Integer.toString(num).toCharArray();
        // for maximum value, replace the first non 9 digit to 9
        // for minimum, we have 2 case,
        // if first letter is 1, then first character which is not 1 should be replaced to 0
        // else first letter > 1 should be relaced with 1. This is because leading 0 is not allowed.
        int right = 0;
        int length = forMax.length;
        while (right < length && forMax[right] == '9') {
            right++;
        }
        int maxValue = 0;
        int minValue = 0;
        if (right == length) {
            maxValue = Integer.parseInt(new String(forMax));
        }
        else {
            char target = forMax[right];
            while (right < length) {
                if (forMax[right] == target)
                    forMax[right] = '9';
                right++;
            }
            maxValue = Integer.parseInt(new String(forMax));
        }
        // System.out.println(maxValue);
        if (forMin[0] - '0' > 1) {
            char target = forMin[0];
            for (int index = 0; index < length; index++) {
                if (forMin[index] == target) {
                    forMin[index] = '1';
                }
            }
            minValue = Integer.parseInt(new String(forMin));
        }
        else {
            right = 0;
            while (right < length && forMin[right] - '0' <= 1) {
                right++;
            }
            if (right == length) {
                minValue = Integer.parseInt(new String(forMin));
            }
            else {
                char target = forMin[right];
                while (right < length) {
                    if (forMin[right] == target)
                        forMin[right] = '0';
                    right++;
                }
                minValue = Integer.parseInt(new String(forMin));
            }
        }
        // System.out.println(minValue);
        return maxValue - minValue;
    }
}