Digit DP with Bitmasking
Intuition\nThe goal is to count how many numbers up to a given number n have repeated digits. To solve this, we use digit DP. \n\nThe idea is to break down the 
# Intuition\nThe goal is to count how many numbers up to a given number `n` have repeated digits. To solve this, we use **digit DP**. \n\nThe idea is to break down the problem digit by digit and track the state of the number being formed.\n\nWe use a bitmask to keep track of which digits have been used so far.\n\n# Approach\nWe define a recursive function `solve()` that explores each digit of the number `n`:\n\n1. **State Variables**:\n   - `pos`: The current index of digit we are processing.\n   - `tight`: Whether we are still bound by the digits of `n` (true if the current prefix of the number is still less than or equal to the corresponding prefix of `n`).\n   - `mask`: A bitmask to track which digits have been used so far (each bit in the mask corresponds to a digit).\n   - `repeated`: A boolean that tracks if any digit has been repeated in the current number.\n\n2. **Recursive Case**:\n   - For each digit in the range of possible digits (`0-9` or `0-upper_bound` based on the `tight` constraint), we either set a digit for the current position or skip to the next state.\n   - If the digit `i` has already been used (tracked using the mask), we set `repeated = true`.\n   - If `i` is a new digit, we mark it in the mask by toggling its corresponding bit.\n   - Leading zeros are handled separately to avoid marking them in the mask.\n\n3. **Base Case**:\n   - When we reach the end of the number (i.e., `pos == str.size()`), we return whether a repeated digit has been found for this number.\n\n4. **DP Memoization**:\n   - We use a 4D DP array `dp[pos][tight][mask][repeated]` to store the results of previously computed states, which avoids redundant calculations.\n\n\n# Complexity\n- **Time complexity**: \n  The time complexity is determined by the number of digits in `n`, which is at most `log10(n)`. For each position (digit), there are at most `2` possible values for `tight` and `repeated`, and `1024` possible bitmasks (since we are using a 10-bit mask for the digits). Hence, the time complexity is approximately $$O(\\log_{10}(n) \\times 2 \\times 1024 \\times 2)$$, which simplifies to $$O(\\log_{10}(n)*(2^n))$$ in practical terms.\n\n- **Space complexity**: \n  The space complexity is determined by the size of the DP table, which has dimensions `log10(n) \xD7 2 \xD7 1024 \xD7 2`, and the recursive stack. Hence, the space complexity is $$O(\\log_{10}(n) \\times 2 \\times 1024 \\times 2)$$, which also simplifies to $$O(\\log_{10}(n)*(2^n))$$.\n\n# Code\n```cpp\nclass Solution {\npublic:\nstring s;\nint sz;\nint dp[10][1<<10][2][2];\n    int dfs(int ind, int mask, bool tight, bool repeated)\n    {\n        if(ind == sz) return repeated;\n        int ub = tight ? s[ind] - \'0\' : 9;\n        if(dp[ind][mask][tight][repeated]!=-1) return dp[ind][mask][tight][repeated];\n        int res = 0;\n        for(int i = 0;i<=ub;i++)\n        {\n            int newMask = mask;\n            if(i != 0 || mask != 0)\n            {\n                newMask = mask | (1<<i);\n            }\n            res += dfs(ind+1,newMask,tight & (i == ub), repeated | (mask&(1<<i)));\n        }\n        return dp[ind][mask][tight][repeated] = res;\n    }\n    int numDupDigitsAtMostN(int n) {\n        int mask = 0;\n        memset(dp,-1,sizeof(dp));\n        bool repeated = false;\n        bool tight = true;\n        s = to_string(n);\n        sz = s.size();\n        return dfs(0,mask,tight,repeated);\n    }\n};
['Recursion', 'Memoization', 'C++']