🧮 Digit DP with Bitmask 🔢 | Time: O(10 × 2^10 × log n) | Space: O(10 × 2^10)
IntuitionThis problem asks to find the number of positive integers less than or equal to n that have at least one repeated digit. A direct approach would be ine
# Intuition

This problem asks to find the number of positive integers less than or equal to `n` that have at least one repeated digit. A direct approach would be inefficient, requiring checking each number from 1 to n. Instead, the solution uses a complementary counting technique: find all numbers with no repeated digits and subtract from n.

The key insight is to use digit-based dynamic programming (Digit DP) with a bitmask to track which digits have already been used, ensuring uniqueness.

# Approach

The solution employs a top-down dynamic programming approach with memoization:

1. Convert the number `n` to a string to process each digit individually
2. Define a recursive function `dp(pos, tight, used, started)` with parameters:
   - `pos`: Current position in the number
   - `tight`: Boolean indicating if current digit is constrained by the original number
   - `used`: Bitmask representing which digits have been used
   - `started`: Boolean indicating if we've started placing non-zero digits

3. Base case: If all positions are filled and we've placed at least one digit, return 1

4. For each position, there are two scenarios:
   - Skip the current position if we haven't started placing digits yet
   - Try placing each valid digit (0-9) if it hasn't been used before

5. Track state using the bitmask `used`, where the i-th bit represents whether digit i has been used

6. Use the `tight` flag to ensure we don't exceed the original number

7. Finally, subtract the count of numbers with unique digits from `n` to get the answer

The memoization table stores results for each state combination, avoiding redundant calculations.

# Complexity

- Time complexity: **O(10 × 2^10 × log n)**
  - Number of digits in n is proportional to log n
  - For each position, we have at most 10 digit choices
  - Bitmask for used digits has 2^10 possible states
  - Each state combination is computed once due to memoization

- Space complexity: **O(10 × 2^10 × log n)**
  - The memoization table stores results for each state: position (log n) × tight (2) × used (2^10) × started (2)
  - This can be simplified to O(10 × 2^10) since the other factors are small constants

# Code
```python3
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)

        memo = {}
        def dp(pos, tight, used, started):
            if pos >= len(s):
                return 1 if started else 0
            
            key = (pos, tight, used, started)
            if key in memo:
                return memo[key]
            
            res = 0
            if not started:
                res += dp(pos + 1, False, used, False)
            
            start = 0 if started else 1
            limit = int(s[pos]) if tight else 9

            for digit in range(start, limit+1):
                if (used >> digit) & 1:
                    continue
                
                new_mask = used | (1 << digit)
                new_tight = tight and (digit == limit)
                res += dp(pos + 1, new_tight, new_mask, True)
            
            memo[key] = res
            return res
        
        
        return n-dp(0, True, 0, False)
```

# Detailed Explanation

The solution leverages Digit DP, a powerful technique for solving problems involving digit constraints:

1. **State Definition**:
   - `pos`: Current position in the number (0-indexed from left)
   - `tight`: Restricts digit choices if we're following n's prefix
   - `used`: Bitmask where the i-th bit is 1 if digit i has been used
   - `started`: Indicates if we've started placing non-zero digits
   
2. **Bit Manipulation**:
   - `(used >> digit) & 1`: Checks if digit is already used
   - `used | (1 << digit)`: Marks digit as used in the bitmask
   
3. **Decision Logic**:
   - If `not started`, we can skip the current position (leading zeros are ignored)
   - For valid digits, we update `new_tight` based on whether the current digit matches the limit
   - The starting digit range is adjusted to avoid leading zeros in numbers

4. **Final Calculation**:
   - `dp(0, True, 0, False)` counts numbers with no repeated digits
   - Subtracting from `n` gives the count of numbers with at least one repeated digit

This approach efficiently handles the counting without explicitly checking each number, making it suitable for large values of n.

---

If you find this editorial helpful, please consider upvoting! ⬆️
['Dynamic Programming', 'Python3']