<p>Given an integer <code>n</code>, return <em>the number of positive integers in the range </em><code>[1, n]</code><em> that have <strong>at least one</strong> repeated digit</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 20
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only positive number (&lt;= 20) with at least 1 repeated digit is 11.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 100
<strong>Output:</strong> 10
<strong>Explanation:</strong> The positive numbers (&lt;= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 1000
<strong>Output:</strong> 262
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    vector<int> a;
    vector<int> b;
    int dp[11][2][2][(1<<11)][2];

    int rec(int level,int l,int r,int mask,int ans){
        //pruning and base case
        if(level == b.size()){
            if(ans == 1) return 1;
            else return 0;
        }

        //cache check
        if(dp[level][l][r][mask][ans] != -1) return dp[level][l][r][mask][ans];

        //transitions
        int sum = 0;

        int lo = 0;
        int hi = 9;

        if(l == 1) lo = a[level];
        if(r == 1) hi = b[level];

        for(int i = lo;i <= hi;i++){
            int tlo = l;
            int thi = r;

            if(i != lo) tlo = 0;
            if(i != hi) thi = 0;

            int x = (mask & (1 << i));

            if(mask == 0){
                if(i == 0){
                    sum = sum + rec(level+1,tlo,thi,mask,ans);
                }
                else{
                    sum = sum + rec(level+1,tlo,thi,(mask | (1<<i)),ans);
                }
            }
            else{
            if(x == 0){
                int val  = mask | (1 << i);
                sum  = sum + rec(level+1,tlo,thi, val, ans);
            }

            else{
                int val = mask;
                sum = sum + rec(level+1,tlo,thi,mask,1);
            }
            }
        }

        //save and return
        return dp[level][l][r][mask][ans] = sum;
    }
    int numDupDigitsAtMostN(int n) {
        memset(dp,-1,sizeof(dp));

        a.push_back(1);
        int x = n;

        while(x != 0){
            b.push_back(x%10);
            x = x/10;
        }

        x = b.size()-a.size();
        for(int i = 0;i < x;i++) a.push_back(0);

        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());

        // for(int i = 0;i < a.size();i++){
        //     cout << a[i] << " ";
        // }
        // cout << "\n";

        // for(int i = 0;i < b.size();i++){
        //     cout << b[i] << " ";
        // }
        // cout << "\n";

        int ans = rec(0,1,1,0,0);

        return ans;
    }
};
8200