Solution Explanation: Numbers With Repeated Digits

This problem asks to find the count of numbers within the range [1, n] that contain at least one repeated digit. The most efficient approach is to use dynamic programming with state compression. Instead of directly counting numbers with repeated digits, we'll count numbers without repeated digits and subtract that from the total numbers (n).

Approach:

1. Digit DP: We'll use a recursive function (dfs in the code) that explores the digits of the numbers from left to right. The function intelligently avoids exploring unnecessary branches by considering limits and leading zeros.

2. State Compression: We use a bitmask (mask) to track which digits have already been used. Each bit in the mask represents a digit (0-9). A bit set to 1 means the digit is already present, and 0 means it's not used yet.

3. Memoization: To avoid redundant calculations, we use memoization (dynamic programming). The dfs function's results are stored in a cache (f in the code) to avoid recomputing the same subproblems.

4. Base Case: The base case for dfs is when all digits of the number have been processed. If there were no leading zeros and no repeated digits, we count this as a valid number (returning 1). Otherwise, we return 0.

5. Recursive Step: The dfs function recursively explores each possible digit (0-9) at each position. It checks:

   • If the digit is allowed (within the limits imposed by n and previous digits).
   • If the digit has not already been used (checking the mask).
   • If it's a leading zero (needs special handling). The function adds up the results from exploring all valid choices.

6. Final Result: The function numDupDigitsAtMostN(n) calls dfs to count numbers without repeated digits and then subtracts this count from n to get the count of numbers with at least one repeated digit.

Time Complexity: O(log n * 210 * 10) ≈ O(10240 * log n). The logarithmic factor comes from the number of digits in n. The 210 represents the possible states of the bitmask (10 digits), and the factor of 10 accounts for the loop iterating through possible digits. Since the input is capped at 109, the logarithmic factor doesn't significantly impact the overall time complexity. Effectively, the runtime is almost constant for all inputs.

Space Complexity: O(log n * 210) ≈ O(1024 * log n). This is due to the memoization table (f).

Code Examples (Python):

from functools import cache
 
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        m = len(s)
 
        @cache
        def dfs(i, mask, lead, limit):
            if i == m:
                return lead ^ 1  # 1 if no leading zeros and no repeated digits, 0 otherwise
 
            up = int(s[i]) if limit else 9
            ans = 0
            for d in range(up + 1):
                if lead and d == 0:
                    ans += dfs(i + 1, mask, True, limit and d == up)
                elif (mask >> d) & 1 == 0:
                    ans += dfs(i + 1, mask | (1 << d), False, limit and d == up)
            return ans
 
        return n - dfs(0, 0, True, True)
 

The code in other languages (Java, C++, Go, TypeScript) follows the same logic with minor syntactic differences to adapt to each language's features. The core algorithm remains consistent across all implementations.