Numbers At Most N Given Digit Set solution and explanation

def atMostNGivenDigitSet(digits, n):
    str_n = str(n)
    L = len(str_n)
    count = 0
    # Count numbers with length less than that of n
    for i in range(1, L):
        count += len(digits) ** i
    
    # Count numbers with the same length as n
    def backtrack(pos, isTight):
        if pos == L:
            return 1
        validNumbers = 0
        for digit in digits:
            if digit < str_n[pos]:
                validNumbers += len(digits) ** (L - pos - 1)
            elif digit == str_n[pos]:
                validNumbers += backtrack(pos + 1, True)
        return validNumbers
    count += backtrack(0, True)    
    return count

digits = ['1', '3', '5', '7']
n = 100
print(atMostNGivenDigitSet(digits, n))

function atMostNGivenDigitSet(digits, n) {
    const strN = n.toString();
    const L = strN.length;
    let count = 0;
    // Count numbers with length less than that of n
    for (let i = 1; i < L; i++) {
        count += Math.pow(digits.length, i);
    }
    
    // Count numbers with the same length as n
    function backtrack(pos, isTight) {
        if (pos === L) return 1;
        let validNumbers = 0;
        for (let digit of digits) {
            if (digit < strN[pos]) {
                validNumbers += Math.pow(digits.length, L - pos - 1);
            } else if (digit === strN[pos]) {
                validNumbers += backtrack(pos + 1, true);
            }
        }
        return validNumbers;
    }
    count += backtrack(0, true);
    return count;
}

const digits = ['1', '3', '5', '7'];
const n = 100;
console.log(atMostNGivenDigitSet(digits, n));

import java.util.*;

public class DigitSet {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String strN = Integer.toString(n);
        int L = strN.length(), m = digits.length;
        int[] dp = new int[L + 1];
        dp[L] = 1;

        for (int i = L - 1; i >= 0; --i) {
            for (String d : digits) {
                if (d.charAt(0) < strN.charAt(i)) {
                    dp[i] += Math.pow(m, L - i - 1);
                } else if (d.charAt(0) == strN.charAt(i)) {
                    dp[i] += dp[i + 1];
                }
            }
        }

        for (int i = 1; i < L; ++i) {
            dp[0] += Math.pow(m, i);
        }

        return dp[0];
    }

    public static void main(String[] args) {
        String[] digits = {"1", "3", "5", "7"};
        int n = 100;
        DigitSet digitSet = new DigitSet();
        System.out.println(digitSet.atMostNGivenDigitSet(digits, n));
    }
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int atMostNGivenDigitSet(vector<string>& digits, int n) {
    string str_n = to_string(n);
    int L = str_n.size(), m = digits.size();
    vector<int> dp(L + 1, 0);
    dp[L] = 1;
    
    for (int i = L - 1; i >= 0; --i) {
        for (string& d : digits) {
            if (d[0] < str_n[i])
                dp[i] += pow(m, L - i - 1);
            else if (d[0] == str_n[i])
                dp[i] += dp[i + 1];
        }
    }
    
    for (int i = 1; i < L; ++i)
        dp[0] += pow(m, i);
    
    return dp[0];
}

int main() {
    vector<string> digits = {"1", "3", "5", "7"};
    int n = 100;
    cout << atMostNGivenDigitSet(digits, n) << endl;
    return 0;
}

function atMostNGivenDigitSet(digits: string[], n: number): number {
    const s = n.toString();
    const m = s.length;
    const f: number[] = Array(m).fill(-1);
    const nums = new Set<number>(digits.map(d => parseInt(d)));
    const dfs = (i: number, lead: boolean, limit: boolean): number => {
        if (i >= m) {
            return lead ? 0 : 1;
        }
        if (!lead && !limit && f[i] !== -1) {
            return f[i];
        }
        const up = limit ? +s[i] : 9;
        let ans = 0;
        for (let j = 0; j <= up; ++j) {
            if (!j && lead) {
                ans += dfs(i + 1, true, limit && j === up);
            } else if (nums.has(j)) {
                ans += dfs(i + 1, false, limit && j === up);
            }
        }
        if (!lead && !limit) {
            f[i] = ans;
        }
        return ans;
    };
    return dfs(0, true, true);
}

func atMostNGivenDigitSet(digits []string, n int) int {
	s := strconv.Itoa(n)
	m := len(s)
	f := make([]int, m)
	for i := range f {
		f[i] = -1
	}
	nums := map[int]bool{}
	for _, d := range digits {
		x, _ := strconv.Atoi(d)
		nums[x] = true
	}
	var dfs func(i int, lead, limit bool) int
	dfs = func(i int, lead, limit bool) int {
		if i >= m {
			if lead {
				return 0
			}
			return 1
		}
		if !lead && !limit && f[i] != -1 {
			return f[i]
		}
		up := 9
		if limit {
			up = int(s[i] - '0')
		}
		ans := 0
		for j := 0; j <= up; j++ {
			if j == 0 && lead {
				ans += dfs(i+1, true, limit && j == up)
			} else if nums[j] {
				ans += dfs(i+1, false, limit && j == up)
			}
		}
		if !lead && !limit {
			f[i] = ans
		}
		return ans
	}
	return dfs(0, true, true)
}