Runtime 75 ms Beats 75.00% [EXPLAINED]
Intuition\nWhen solving this problem, I want to find out how many numbers from 1 to \uD835\uDC5B have at least one repeated digit. Instead of counting these num
# Intuition\nWhen solving this problem, I want to find out how many numbers from 1 to \uD835\uDC5B have at least one repeated digit. Instead of counting these numbers directly (which is hard), I use a clever trick: I count how many numbers up to \uD835\uDC5B don\'t have repeated digits, and then subtract this from \uD835\uDC5B.\n\n\n# Approach\nConvert n to a String: Makes digit handling easier.\n\nRecursive Search: Explore numbers with unique digits using a bitmask to track used digits and a DP table to avoid redundant work.\n\nCount and Subtract: Count unique-digit numbers and subtract from n.\n\n# Complexity\n- Time complexity:\nO(n x 2d), where d is the number of digits in n.\n\n\n- Space complexity:\nO(d x 2d) for the DP table.\n\n# Code\n```typescript []\nfunction numDupDigitsAtMostN(n: number): number {\n    const s = n.toString();\n    const len = s.length;\n    const dp = Array.from({ length: len }, () => Array(1 << 10).fill(-1));\n    \n    const dfs = (index: number, mask: number, isLimit: boolean, hasLeadingZeros: boolean): number => {\n        // Base case: reached the end of the number\n        if (index === len) return hasLeadingZeros ? 0 : 1;\n\n        // Return cached result if not constrained by limits\n        if (!isLimit && !hasLeadingZeros && dp[index][mask] !== -1) {\n            return dp[index][mask];\n        }\n\n        // Initialize result for the current state\n        let count = 0;\n\n        // If there are leading zeros, skip to the next digit\n        if (hasLeadingZeros) {\n            count += dfs(index + 1, mask, false, true);\n        }\n\n        // Define range for the current digit\n        const low = hasLeadingZeros ? 1 : 0;\n        const high = isLimit ? +s[index] : 9;\n\n        // Try all possible digits for the current position\n        for (let digit = low; digit <= high; digit++) {\n            if ((mask & (1 << digit)) === 0) { // Check if digit is not used\n                count += dfs(index + 1, mask | (1 << digit), isLimit && digit === high, false);\n            }\n        }\n\n        // Cache result for the current state if not constrained by limits\n        if (!isLimit && !hasLeadingZeros) {\n            dp[index][mask] = count;\n        }\n\n        return count;\n    };\n\n    // Total numbers with unique digits up to `n`\n    return n - dfs(0, 0, true, true);\n}\n\n```
['TypeScript']