<p>We call a positive integer <strong>special</strong> if all of its digits are <strong>distinct</strong>.</p>

<p>Given a <strong>positive</strong> integer <code>n</code>, return <em>the number of special integers that belong to the interval </em><code>[1, n]</code>.</p>

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

<pre>
<strong>Input:</strong> n = 20
<strong>Output:</strong> 19
<strong>Explanation:</strong> All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
</pre>

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

<pre>
<strong>Input:</strong> n = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong> All the integers from 1 to 5 are special.
</pre>

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

<pre>
<strong>Input:</strong> n = 135
<strong>Output:</strong> 110
<strong>Explanation:</strong> There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.</pre>

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

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

def countDistinctNumbers(digits):
    if digits == 0:
        return 0
    
    total = 0

    for i in range(1, digits + 1):
        curr = 9
        
        for j in range(i - 1):
            curr *= (9 - j)

        total += curr

    return total

def totalDigits(num):
    if num == 0:
        return 1
    
    cnt = 0
    while num > 0:
        num = int(num / 10)
        cnt += 1

    return cnt

def allDigits(num):
    digits = []
    
    while num > 0:
        d = int(num % 10)
        digits.append(d)
        num = int(num / 10)
    
    return list(reversed(digits))

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        digits = allDigits(n)
        nDigits = len(digits)
        total = countDistinctNumbers(nDigits - 1)
        visited = [False for x in range(10)]

        # print("total = ", total)

        for i, d in enumerate(digits):
            # print("i=", i, ", d=", d)
            curr = d - 1 if i == 0 else d

            for j in range(i):
                if digits[j] < d:
                    curr -= 1
            
            # print("curr = ", curr)

            for j in range(i + 1, len(digits)):
                # print("curr *= ", 10 - j)
                curr *= (10 - j)

            total += curr

            if visited[d]:
                break

            visited[d] = True
            # print("total = ", total)

        # for i in range(pow(10, nDigits - 1), n + 1):
        #     curr = i
        #     visited = [False for x in range(10)]

        #     while curr:
        #         d = int(curr % 10)
        #         if visited[d]:
        #             break
                
        #         visited[d] = True
        #         curr = int(curr / 10)
            
        #     if curr == 0:
        #         total += 1
        visited = [False for i in range(10)]
        nonRepeat = True

        for d in digits:
            if visited[d]:
                nonRepeat = False
                break
            
            visited[d] = True

        if nonRepeat:
            total += 1
            
        return total
43