<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>

typedef long long int ll;

class Solution {
public:

    int numDupDigitsAtMostN(int N) {

        int ans = 0;

        string s = to_string(N);
        reverse( s.begin(), s.end());

        int n = s.length();

        vector< vector<int> > arr( 11, vector<int>());

        for( int i=0; i<1024; i++) {
            int bc = __builtin_popcount(i);
            arr[bc].push_back(i);
        }

        vector< vector<int> > dp( 1024, vector<int>( 10, 0));

        for( int i=0; i<10; i++) {
            dp[1<<i][i] = 1;
        }
        for( int l=1; l<10; l++) {
            for( int mask: arr[l]) {
                int tot = 0;
                for( int b=0; b<10; b++) {
                    tot += dp[mask][b];
                }
                for( int b=0; b<10; b++) {
                    if(mask&(1<<b)) {
                        continue;
                    }
                    dp[mask^(1<<b)][b] += tot;
                }
            }
        }

        for( int l=1; l<n; l++) { 
            for( int mask: arr[l]) {
                for( int d=1; d<10; d++) {
                    ans += dp[mask][d];
                }
            }
        }

        bool v = true;
        int seen = 0;

        for( int i=n-1; i>=0; i--) {
            int td = s[i]-'0';
            for( int mask: arr[i+1]) {
                if(seen&mask) {
                    continue;
                }
                for( int d=(i==n-1); d<td; d++) {
                    ans += dp[mask][d];
                }
            }
            if(seen&(1<<td)) {
                v = false;
                break;
            }
            seen = seen^(1<<td);
        }

        ans += v;

        return N-ans;
    }
};
24400