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

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        def get_digits(num):
            ans = []
            while num > 9:
                dt = num % 10
                ans.insert(0, dt)
                num -= dt
                num //= 10

            if num != 0:
                ans.insert(0, num)

            return ans

        def get_distinct_count(length):
            if length < 1 or length > 10:
                raise ValueError(f"Invalid length: {length}")
            elif length == 1:
                return 9

            sum_ = 9  # the top digit range can ONLY be [1, 9]
            digits_remain = 9
            length -= 1
            while length > 0:
                sum_ *= digits_remain
                digits_remain -= 1
                length -= 1

            return sum_

        def get_distinct_count_plus(remain_len, current_digit, taken_digits, is_first=False):
            current_digit_choices = 0
            is_last_digit = remain_len == 0
            start = 1 if is_first else 0
            end = current_digit if is_last_digit else current_digit - 1

            for j in range(start, end + 1):
                if j in taken_digits:
                    continue
                current_digit_choices += 1

            remain_digits_combination = 1
            remain_digits = 10 - len(taken_digits) - 1
            while remain_len > 0:
                remain_digits_combination *= remain_digits
                remain_digits -= 1
                remain_len -= 1

            return current_digit_choices * remain_digits_combination

        if n < 10:
            return n

        digits = get_digits(n)
        LEN = len(digits)
        ans = 0

        # first, count [Special Number] of length 1, 2, to LEN - 1
        for i in range(1, LEN):
            ans += get_distinct_count(i)

        # now, we need to count [Special Number] of length LEN
        taken_digits = set()
        for i in range(LEN):
            digit = digits[i]
            ans += get_distinct_count_plus(LEN - 1 - i, digit, taken_digits, i == 0)

            if digit in taken_digits:
                break
            else:
                taken_digits.add(digit)

        return ans
44