Count Numbers With Unique Digits II - Solution & Explanation

The problem asks to count how many numbers in the range [a, b] have unique digits. We can solve this problem using state compression and digit DP.

We can use a function f(n) to count how many numbers in the range [1, n] have unique digits. Then the answer is f(b) - f(a - 1).

In addition, we can use a binary number to record the digits that have appeared in the number. For example, if the digits 1, 3, 5 have appeared in the number, we can use 10101 to represent this state.

Next, we use memoization search to implement digit DP. We search from the starting point to the bottom layer to get the number of schemes, return the answer layer by layer and accumulate it, and finally get the final answer from the search starting point.

The basic steps are as follows:

1. We convert the number n into a string num, where num[0] is the highest digit and num[len - 1] is the lowest digit.
2. Based on the problem information, we design a function dfs(pos, mask, limit), where pos represents the current processing position, mask represents the digits that have appeared in the current number, and limit represents whether there is a limit at the current position. If limit is true, then the digit at the current position cannot exceed num[pos].

The answer is dfs(0, 0, true).

The time complexity is O(m times 2^{10} times 10), and the space complexity is O(m times 2^{10}). Where m is the number of digits in b.