Problem statement

https://leetcode.com/problems/numbers-with-repeated-digits/

Solution

The idea is to go digit by digit and construct answer using usual digit build approach. For example for N + 1 = 142857, we have

  1. 14285?, where ? < 7
  2. 1428?*, where ? < 5 and * is any digit.
  3. 142?**, where ? < 8 and * is any digit.

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