Problem Description

You are given an integer num. You need to apply a digit replacement operation to this number twice to create two different numbers a and b.

The digit replacement operation works as follows:

• Choose a digit x (where 0 <= x <= 9) that appears in the number
• Choose another digit y (where 0 <= y <= 9) to replace it with (note that y can equal x)
• Replace all occurrences of digit x in the number with digit y

You apply this operation independently two times on the original num to get:

• Number a from the first operation
• Number b from the second operation

Your goal is to maximize the difference between a and b, and return this maximum difference.

Important constraints:

• Neither a nor b can have leading zeros
• Neither a nor b can be 0

For example, if num = 555:

• You could replace all 5s with 9s to get a = 999
• You could replace all 5s with 1s to get b = 111
• The maximum difference would be 999 - 111 = 888

The strategy to maximize the difference is to make a as large as possible and b as small as possible. To make a largest, find the first non-9 digit from left to right and replace all its occurrences with 9. To make b smallest, if the first digit isn't 1, replace all occurrences of it with 1; otherwise, find the first digit (after the leading digit) that isn't 0 or 1 and replace all its occurrences with 0.

Intuition

To maximize the difference between two numbers, we need to make one as large as possible and the other as small as possible.

For maximizing a number, we want to replace digits with the largest possible digit, which is 9. But which digit should we replace? If we scan from left to right (most significant to least significant), the first digit that isn't already 9 is our best candidate. Why? Because changing a more significant digit has a larger impact on the final value. For instance, changing 555 to 955 (first digit to 9) gives us 955, while changing it to 559 (last digit to 9) only gives us 559.

For minimizing a number, we want to replace digits with the smallest possible digit. However, we have constraints:

• We can't have leading zeros (so the first digit can't become 0)
• The result can't be 0

This means:

• If the first digit isn't 1, we should replace all occurrences of it with 1 (the smallest non-zero digit)
• If the first digit is already 1, we need to look at the remaining digits. We find the first digit that isn't 0 or 1 and replace all its occurrences with 0

Why do we skip digits that are already 0 or 1 when the first digit is 1? Because:

• Replacing 0 with anything would increase the number (not minimize it)
• Replacing 1 with 0 would also change our leading 1 to 0 (creating a leading zero problem)

The key insight is that we perform these operations independently on the original number, not sequentially. This allows us to optimize each transformation separately without one affecting the other.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows a greedy approach to find the maximum and minimum possible values through digit replacement.

Finding the Maximum Value (a):

1. Convert the number to a string: a = str(num)
2. Iterate through each character (digit) in the string from left to right
3. Find the first digit that is not 9
4. Replace all occurrences of that digit with 9 using a.replace(c, "9")
5. Break after the first replacement since we've maximized the number

Finding the Minimum Value (b):

1. Convert the number to a string: b = str(num)
2. Check the first digit b[0]:
   • If it's not 1, replace all occurrences of the first digit with 1 using b.replace(b[0], "1")
   • This ensures we get the smallest possible number without leading zeros
3. If the first digit is already 1:
   • Iterate through the remaining digits b[1:] from position 1 onwards
   • Find the first digit that is not 0 or 1 (checking c not in "01")
   • Replace all occurrences of that digit with 0 using b.replace(c, "0")
   • Break after finding and replacing the first such digit

Computing the Result:

• Convert both strings back to integers: int(a) and int(b)
• Return the difference: int(a) - int(b)

The algorithm uses string manipulation for easy digit replacement since Python's str.replace() method automatically handles all occurrences of a character. The time complexity is O(n) where n is the number of digits, and the space complexity is O(n) for storing the string representations.

Example Walkthrough

Let's walk through the solution with num = 1234:

Finding Maximum Value (a):

1. Convert to string: a = "1234"
2. Scan from left to right:
   • First digit is '1' (not '9') → Found our target!
3. Replace all '1's with '9': a = "9234"
4. Result: a = 9234

Finding Minimum Value (b):

1. Convert to string: b = "1234"
2. Check first digit: b[0] = '1'
   • It's already '1', so we need to look at remaining digits
3. Scan from position 1 onwards:
   • b[1] = '2' → Check if it's in "01" → No, it's not!
   • Found our target digit '2'
4. Replace all '2's with '0': b = "1034"
5. Result: b = 1034

Final Answer:

• Maximum difference = 9234 - 1034 = 8200

Let's verify with another example, num = 9999:

Finding Maximum Value (a):

1. Convert to string: a = "9999"
2. Scan from left to right:
   • All digits are '9' → No replacement needed
3. Result: a = 9999

Finding Minimum Value (b):

1. Convert to string: b = "9999"
2. Check first digit: b[0] = '9' (not '1')
3. Replace all '9's with '1': b = "1111"
4. Result: b = 1111

Final Answer:

• Maximum difference = 9999 - 1111 = 8888

Solution Implementation

Time and Space Complexity

The time complexity is O(log num) because:

• Converting an integer to a string requires O(log num) time, as the number of digits in the integer is proportional to log num
• The for loops iterate through the string representation, which has O(log num) characters
• The replace() operation on a string of length O(log num) takes O(log num) time
• Converting the string back to an integer also takes O(log num) time

The space complexity is O(log num) because:

• The string representations a and b each store O(log num) characters, where the number of digits is proportional to log num
• The intermediate strings created during the replace() operations also require O(log num) space
• No additional data structures that scale with input size are used

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Single-Digit Edge Cases

When the input is a single digit like 9, the maximization loop might not replace anything since the only digit is already 9. Similarly, for minimization with input 1, both conditions might fail to replace anything.

Example:

• Input: num = 9
• After maximization: a = 9 (no change)
• After minimization: b = 9 (no change because first digit is not 1, but replacing 9 with 1 gives us b = 1)
• Result: 9 - 1 = 8

Solution: The current code actually handles this correctly because replace() will still work even if we're replacing the first (and only) digit.

Pitfall 2: Incorrect Understanding of "All Occurrences"

A common mistake is replacing only the first occurrence of a digit instead of all occurrences. The problem explicitly states that ALL occurrences of the chosen digit must be replaced.

Example:

• Input: num = 1551
• Wrong approach: Replace only first 5 with 9 to get 1951
• Correct approach: Replace ALL 5s with 9 to get 1991

Solution: Always use str.replace() which replaces all occurrences by default, not just manual character-by-character replacement.

Pitfall 3: Creating Leading Zeros in Minimization

When trying to minimize, you might be tempted to replace the first digit with 0, which would create an invalid number with leading zeros.

Example:

• Input: num = 555
• Wrong: Replace all 5s with 0 to get 000 (invalid)
• Correct: Replace all 5s with 1 to get 111

Solution: The code correctly checks if the first digit is not 1 and replaces it with 1 (never 0). Only non-first-digit occurrences can be replaced with 0.

Pitfall 4: Forgetting Break Statements

Without break statements after finding the first replaceable digit, the code might perform multiple replacements, which violates the "single operation" requirement.

Example:

• Input: num = 123
• Wrong (without breaks):
  • Replace 1 with 9: 923
  • Then replace 2 with 9: 993
  • Then replace 3 with 9: 999
• Correct (with break after first replacement): Replace only 1 with 9: 923

Solution: Always include break statements after performing the replacement operation to ensure only one digit type is replaced per operation.