Problem statement

https://binarysearch.com/problems/Repeating-Numbers/

Solution

Equal to Leetcode 1012 Numbers With Repeated Digits

Complexity

It is O(m * k), where m is number of digits in N and k is the size of alphabet.

Code

class Solution:
    def solve(self, N):
        L = list(map(int, str(N + 1)))
        res, n = 0, len(L)

        def A(m, n):
            return 1 if n == 0 else A(m, n - 1) * (m - n + 1)
        
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += A(9 - i, n - i - 1)
            if x in s: break
            s.add(x)
            
        for i in range(1, n): res += 9 * A(9, i - 1)
        return N - res