<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:
        def count_numbers_with_unique_digits(x):
            # Convert number to string for easier digit manipulation
            s = str(x)
            n = len(s)
            
            # Initialize dp array to store counts
            dp = [[-1 for _ in range(1 << 10)] for _ in range(n)]
            
            # Helper function to count numbers with unique digits
            def dfs(pos, mask, is_limit, is_num):
                if pos == n:
                    return is_num  # Return 1 if it's a valid number, 0 otherwise
                
                if not is_limit and is_num and dp[pos][mask] != -1:
                    return dp[pos][mask]
                
                res = 0
                up = int(s[pos]) if is_limit else 9
                for digit in range(up + 1):
                    if (mask >> digit) & 1 == 0:
                        if not is_num and digit == 0:
                            res += dfs(pos + 1, mask, is_limit and digit == up, False)
                        else:
                            res += dfs(pos + 1, mask | (1 << digit), is_limit and digit == up, True)
                
                if not is_limit and is_num:
                    dp[pos][mask] = res
                
                return res
            
            return dfs(0, 0, True, False)
        
        # Total count of numbers in range [1, n]
        total_count = n
        
        # Count of numbers with no repeated digits in range [1, n]
        unique_count = count_numbers_with_unique_digits(n)
        
        # Count of numbers with at least one repeated digit
        return total_count - unique_count

# Example usage:
solution = Solution()
print(solution.numDupDigitsAtMostN(20))  # Output: 1
print(solution.numDupDigitsAtMostN(100))  # Output: 10
print(solution.numDupDigitsAtMostN(1000))  # Output: 262
20200