Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.
Example 1:
Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
Example 2:
Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
Example 3:
Input: 1000
Output: 262
Note:
1 <= N <= 10^9
class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        N = str(N)
        
        @lru_cache(None)
        def dfs(i, r, m):
            if i == len(N):
                return 1
            
            ans = 0
            limit = int(N[i]) if r else 9
            for k in range(0,limit+1):
                if m & (1 << k) == 0:
                    mask =  m | (1 << k) if m or k > 0 else 0
                    if k < limit or not r:
                        ans += dfs(i+1, False, mask)
                    else:
                        ans += dfs(i+1, True, mask)
            return ans
        
        return int(N) - dfs(0, True, 0) + 1
class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        N = str(N)
        
        @lru_cache(None)
        def dfs(i, r, m):
            if i == len(N):
                return 1
            
            ans = 0
            limit = int(N[i]) if r else 9
            for k in range(0,limit+1):
                if m & (1 << k) == 0:
                    mask =  m | (1 << k) if m or k > 0 else 0
                    if k < limit or not r:
                        ans += dfs(i+1, False, mask)
                    else:
                        ans += dfs(i+1, True, mask)
            return ans
        
        return int(N) - dfs(0, True, 0) + 1