Digit Set - Implementation

function atMostNGivenDigitSet(digits, n)
    s := string(n)
    len := length of s
    dp := 2D (two-dimensional) array [len + 1][2], all -1
    // cache to avoid recomputing
    // Count numbers with fewer digits
    result := 0
    for length from 1 to len - 1
        result := result + (size of digits)^length
    // Count numbers with same length as n
    result := result + solve(0, true, s, digits)
    return result

function solve(pos, tight, s, digits)
    if pos = length of s then
        return 1
    t := 1 if tight else 0
    if dp[pos][t] ≠ -1 then
        return dp[pos][t]
    limit := s[pos] if tight else '9'
    count := 0
    for d in digits
        if d > limit then
            break
        if d < limit then
            count := count + solve(pos + 1, false, s, digits)
        else
            count := count + solve(pos + 1, tight, s, digits)
    dp[pos][t] := count
    return count

Time complexity: $O(\log N)$ positions times $|D|$ digits per position.

Space complexity: $O(\log N)$ for the DP table.