Count Special Integers — LeetCode 2376 Python Solution

The problem

We call a positive integer special if all of its digits are distinct. Given a positive integer n, return the number of special integers that belong to the interval [1, n].

Example

Input

n = 20

Output

19

Explanation

All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Python solution

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        @cache
        def dfs(i: int, mask: int, lead: bool, limit: bool) -> int:
            if i >= len(s):
                return int(lead ^ 1)
            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                if mask >> j & 1:
                    continue
                if lead and j == 0:
                    ans += dfs(i + 1, mask, True, limit and j == up)
                else:
                    ans += dfs(i + 1, mask | 1 << j, False, limit and j == up)
            return ans

        s = str(n)
        return dfs(0, 0, True, True)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2376. Count Special Integers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems