Special Integers - Implementation

Solution:

function countSpecialNumbers(n)
    s := string(n)
    len := length of s
    dp := 4D array [len + 1][2][2][1024], all -1
    return solve
function solve
    if pos = length of s then
        return 1 if started else 0
    t := 1 if tight else 0
    st := 1 if started else 0
    if dp[pos][t][st][mask] ≠ -1 then
        return dp[pos][t][st][mask]
    limit := s[pos] if tight else 9
    count := 0
    for d from 0 to limit
        if started and (mask & (1 << d)) ≠ 0 then
            continue
        if not started and d = 0 then
            count := count + solve
        else
            newMask := mask | (1 << d)
            newTight := tight and (d = limit)
            count := count + solve
    dp[pos][t][st][mask] := count
    return count

Time: $O(\log N \cdot 2^{10})$. Space: $O(\log N \cdot 2^{10})$ for the $4$D memoization table.