Given a set of allowed digits and an integer n, return how many positive integers less than or equal to n can be formed using only the allowed digits. Pattern focus: Digit DP. Decide digit by digit while respecting the tight prefix constraint.
digits = allowed digit strings, n = upper bound
count of positive integers <= n formed using only digits
Example 1:
Input:
digits = ["1","3","5","7"] n = 100
Output:
20
Explanation:
There are 20 valid numbers that can be formed and are at most 100.
Example 2:
Input:
digits = ["1","4","9"] n = 1
Output:
1
Explanation:
Only the number 1 is valid.
Example 3:
Input:
digits = ["7"] n = 8
Output:
1
Explanation:
Only the number 7 can be formed.