<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:
        """
        This works by splitting the main interval [1, n] into different intervals.
        For example, take the input n = 3142.
        The first portion of intervals expand by orders of magnitude:
        [1, 10), [10, 100), ..., up to [1000, 3000).
        Each of these intervals (except the last) can be split up into 9 different sub-intervals:
        so [10, 100) has the sub-intervals [10, 20), [20, 30), ..., [90, 100).
        Once we hit the first significant digit, we contract the sub-intervals
        based on each successive digit:
        [3000, 3100), [3100, 3140), [3140, 3142), and finally just [3142].
        """
        # base case, since if n < 11, all numbers below n are special
        if n <= 10:
            return n

        # temporary variables
        digit_list = [int(digit) for digit in str(n)]
        num_digits = len(digit_list)
        total_count = 0
        special_ints = 1 # how many special ints are there per "sub-interval"?
        
        # count up to first significant digit (i.e., [1, 3000) if n = 3142)
        for i in range(num_digits):
            if i + 1 == num_digits:
                total_count += special_ints * (digit_list[0] - 1)
            else:
                total_count += special_ints * 9
                special_ints *= 9 - i  # this decreases bc each new digit reduces num of options
        
        # count rest of digits up to n (i.e. [3000, 3142) if n = 3142)
        used_digits = [digit_list[0]]
        for i, digit in enumerate(digit_list[1:], start=1):
            special_ints //= 10 - i
            # don't count any sub-intervals where we repeat digits!
            multiplier = digit - sum(digit > d for d in used_digits)
            total_count += special_ints * multiplier
            # if we encounter a repeated digit in our number n, stop now!
            if digit in used_digits:
                return total_count
            used_digits.append(digit)
        
        # count n if it's special! (i.e., the last interval [3142])
        if digit_list[-1] not in digit_list[:-1]:
            total_count += 1
        return total_count

26