<p>Given an integer <code>n</code>, return <em>the number of positive integers in the range </em><code>[1, n]</code><em> that have <strong>at least one</strong> repeated digit</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 20
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only positive number (&lt;= 20) with at least 1 repeated digit is 11.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 100
<strong>Output:</strong> 10
<strong>Explanation:</strong> The positive numbers (&lt;= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 1000
<strong>Output:</strong> 262
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        """
        initially suppose we are generating 001, 002, 003 then we dont want to count the leading 0s
        as repeating digits, and for that we will use a different parameter LeadingZeros, which will help us in deffining
        is we are having leading zeros
        """



        nums = [*(str(n))] #--> 20 --> ["2", "0"]
        # dp = [[[[-1]*(1<<10)]*2]*2]*len(nums)
        dp = {}

        

        def funct(index, tight , hasRepeated, mask):
            # when our index reach end of input array we return 0
            # becase we wont be having any repeated digit

            if index == len(nums):
                # now that we have generated our number we can check if it has more than 1 digit repeating  
                if hasRepeated:
                    return 1
                else:
                    # print(num)
                    return 0
            
            upper_limit = int(nums[index]) if tight else 9
            ans = 0
            
            print(index, tight, hasRepeated, mask)
            # if dp[index][last][hasRepeated][mask]!=-1:
            #     return dp[index][last][hasRepeated][mask]
            if (index, tight, hasRepeated, mask) in dp:
                return  dp[(index, tight, hasRepeated, mask)]

            for digit in range(upper_limit + 1):  # get digits from 0-----upper_limit

                # if we are alreading having leading zeros previously then if we add another 0 then
                # it'll be part of that leading zero itself
                # mask zero signifies that we havent started any number till now
                # so when we have our dgit 0 and mask 0 then we are just adding another 0 to the leading zeros
                if digit == 0 and mask == 0:
                    ans += funct(index+1, tight & (digit == upper_limit), False, mask)

                # otherwise we check is the current digit is repeated or not using the mask
                # if current digit is repeated then that digit will be marked in mask so we check that
                elif (mask & (1 << digit)):
                    ans += funct(index+1, tight & (digit == upper_limit), True, mask)
                
                # otherwise mark the current digit in the mask
                else:
                    ans += funct(index+1, (tight & (digit == upper_limit)), hasRepeated, mask | 1 << digit)
            
            dp[(index, tight, hasRepeated, mask)] =  ans
            return dp[(index, tight, hasRepeated, mask)]
            
        
        return funct(0, True, False, 0) # index 0, tight constraint is present for starting index, repeatednumber is False
                                        # mask will be 0 initially
27500