Track repeat using bit mask then digit dp
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can keep a track of digits used so far using a bit mask and if digit we are trying t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can keep a track of digits used so far using a bit mask and if digit we are trying to use now is already set in the bit mask then set the \'repeat\' variable to 1 (or true)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDigit dp with mask. We also need a nz (non-zero) tracker, as for the leading 0s we should not set the bit mask to 1.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(1024 x logn) # base 10\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(1024 x logn) # base 10\n\n# Code\n```python3 []\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        @cache        \n        def dp(i, num, less, mask, rep, nz):\n            if i==len(num):\n                if rep and mask!=1: return 1\n                return 0\n            res = 0\n            for j in range(10):\n                new_mask = mask\n                if not (nz==0 and j==0):\n                    new_mask = mask|(1<<j)\n                new_rep = rep\n                if mask&(1<<j):\n                    new_rep = 1\n\n                if j<int(num[i]):\n                    res+=dp(i+1, num, 1, new_mask, new_rep, nz|(j!=0))\n                elif j==int(num[i]):\n                    res+=dp(i+1, num, less, new_mask, new_rep, nz|(j!=0))\n                elif less:\n                    res+=dp(i+1, num, 1, new_mask, new_rep, nz|(j!=0))\n            return res\n        return dp(0, str(n), 0, 0, 0, 0)\n```
['Python3']