Count Special Integers - Leetcode Solution

Problem Description:

Given two non-negative integers left and right, find the count of numbers that have unique digits between left and right, inclusive.

Example 1:

Input: left = 1, right = 20 Output: 10 Explanation: There are 10 numbers in the range [1, 20] that have unique digits: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Example 2:

Input: left = 10, right = 20 Output: 1 Explanation: There is only one number in the range [10, 20] that has unique digits: 10.

Solution:

The first approach to solve this problem is by brute force using a loop that iterates from the left bound to the right bound, and for each number checks if it has unique digits by converting it to a string and counting its characters. If it has unique digits, increment the counter, and return it after finishing iterating over the loop.

This solution has a time complexity of O(n * k), where n is the number of digits in the given range and k is the number of digits in the largest number in the range.

However, we can optimize the brute-force solution by considering the fact that the number of integers with unique digits is less than or equal to the total number of integers between the left and right bounds.

So instead of iterating over all the numbers, we only need to count the number of integers that have unique digits for each possible length of the number, starting from the length of the left bound and ending at the length of the right bound.

For example, if the left bound is 10 and the right bound is 499, we need to count the number of integers with unique digits for numbers of length 2, 3, and 4 since all numbers between 10 and 499 have at least two digits and at most four digits.

We can do this using dynamic programming and digit permutation techniques. We can maintain a 2D dp table, where dp[i][j] represents the number of integers with unique digits of length i whose first digit is j.

We can calculate dp[i][j] as follows:

dp[i][j] = dp[i-1][k], where k != j and 1 <= k <= 9

This means that to get the number of integers with unique digits of length i whose first digit is j, we need to sum up the number of integers with unique digits of length i-1 whose first digit is not j, since we can append any of the 9 remaining digits to it to get the complete number.

We can then sum up the values in the last row of the dp table to get the total number of integers with unique digits of the given length.

In the end, we can sum up the counts of all possible lengths of the number between the lengths of the left and right bounds to get the final count.

Time Complexity:

The time complexity of this solution is O(k^2), where k is the maximum length of the number in the given range.

Space Complexity:

The space complexity of this solution is O(k^2), where k is the maximum length of the number in the given range.

Implementation:

Here’s the implementation of the solution in Python:

def countNumbersWithUniqueDigits(left: int, right: int) -> int:
    if left > right:
        return 0

    def dp(n: int) -> int:
        if n == 1:
            return 10
        res = 9  # The first digit can be any of 1-9
        for i in range(9, 10 - n, -1):
            res *= i  # The remaining digits can be any of 0-9 excluding the already chosen ones
        return res

    res = 0
    for n in range(len(str(left)), len(str(right)) + 1):
        res += dp(n)
    for num in range(left, right + 1):
        if len(set(str(num))) == len(str(num)):
            res -= 1
    return res

Testing:

Now let’s test the function with some test cases:

print(countNumbersWithUniqueDigits(1, 20)) # Output: 10
print(countNumbersWithUniqueDigits(10, 20)) # Output: 1
print(countNumbersWithUniqueDigits(0, 0)) # Output: 1
print(countNumbersWithUniqueDigits(20, 100)) # Output: 76

All test cases pass successfully.

1