<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:
  # Same as 1012. Numbers With Repeated Digits
  def countSpecialNumbers(self, n: int) -> int:
    s = str(n)

    @functools.lru_cache(None)
    def dp(i: int, used: int, isTight: bool) -> int:
      """
      Returns the number of special integers, considering the i-th digit, where
      `used` is the bitmask of the used digits, and `isTight` indicates if the
      current digit is tightly bound.
      """
      if i == len(s):
        return 1

      res = 0

      maxDigit = int(s[i]) if isTight else 9
      for d in range(maxDigit + 1):
        # `d` is used.
        if used >> d & 1:
          continue
        # Use `d` now.
        nextIsTight = isTight and (d == maxDigit)
        if used == 0 and d == 0:  # Don't count leading 0s as used.
          res += dp(i + 1, used, nextIsTight)
        else:
          res += dp(i + 1, used | 1 << d, nextIsTight)

      return res

    return dp(0, 0, True) - 1  # - 0
207