<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:
    int dp[11][2][2][1<<10][2];
    // 5th state that taken 0 is valid or not (means front 0 can be repeatative)
    int rec(int i, int l, int h, int taken, int z, string &L, string &R)
    {
        if(dp[i][l][h][taken][z] != -1)
            return dp[i][l][h][taken][z];
        
        int len = L.size();
        if(i == len)
        {
            // cout << "done"<< endl;
            return 1;
        }

        int l_lim = 0, h_lim = 9;
        if(l == 1)
            l_lim = L[i]-'0';
        if(h == 1)
            h_lim = R[i]-'0';

        int ans = 0;
        for(int j = l_lim; j <= h_lim; j++)
        {
            int nl = l, nh = h;
            if(j != L[i]-'0')
                nl = 0;
            if(j != R[i]-'0')
                nh = 0;

            // can we take j as a digit
            if(z == 0)
            {
                if(j == 0)
                    ans += rec(i+1, nl, nh, 0, 0, L, R);
                else
                    ans += rec(i+1, nl, nh, ((taken)|(1<<j)), 1, L, R);
            }
            else
            {
                if( ((taken)&(1<<j)) == 0)
                // cout << "j\n";
                    ans += rec(i+1, nl, nh, ((taken)|(1<<j)), 1, L, R);
            }
        }
        dp[i][l][h][taken][z] = ans;
        return ans;
    }
    int numDupDigitsAtMostN(int n)
    {
        // count number of no repeated digit


        string R = to_string(n);
        string L = string(R.size()-1, '0') + "1";
        // cout << L << endl;

        memset(dp, -1, sizeof(dp));

        return n - rec(0, 1, 1, 0, 0, L, R);
    }
};
8100