Count Special Integers

A much more efficient method is to use digit dynamic programming, which builds the count based on the digits of n. Instead of checking every number, we can count the number of valid special integers mathematically. We can count the special integers with fewer digits than n and then count the special integers with the same number of digits as n but are less than or equal to n.

The problem is to count special numbers up to n. This can be solved using digit dynamic programming and combinatorics. Let S be the string representation of n and L be its length.

The count is divided into two parts:

1. Count special numbers with fewer digits than n:

   • Iterate for each length d from 1 to L-1.
   • For a d-digit number, the first digit has 9 choices (1-9). The remaining d-1 digits are a permutation of d-1 digits chosen from the 9 remaining available digits (0-9 excluding the first digit).
   • The count for length d is 9 * P(9, d-1), where P(m, k) is the number of k-permutations of m.
   • Sum these counts for all d < L.

2. Count special numbers with the same number of digits as n and are less than or equal to n:

   • Iterate through the digits of n from left to right (index i from 0 to L-1).
   • Maintain a set of digits seen in the prefix.
   • At each position i, consider placing a digit d that is smaller than the digit n[i].
   • For each such valid d (not 0 for the first position and not in seen), the remaining L-1-i positions can be filled in P(10 - (i+1), L-1-i) ways. Add this to the total count.
   • After checking smaller digits, check the digit n[i] itself. If n[i] is already in seen, it means n and any other number with this prefix is not special. We must stop and return the current count.
   • If n[i] is not in seen, add it to seen and proceed to the next position i+1.

3. Final check for n:

   • If the loop completes, it means n itself is a special number. Increment the final count by 1.

Let's illustrate with n = 135. The string is S = "135" and length L = 3.

Part 1: Count special numbers with length < 3

• 1-digit numbers: 9 (1-9).
• 2-digit numbers: The first digit has 9 choices (1-9). The second has 9 choices (0-9, excluding the first). Total: 9 * 9 = 81.
• Total for length < 3: 9 + 81 = 90.

Part 2: Count 3-digit special numbers <= 135

• We iterate through S = "135".
• Position 0 (hundreds): S[0] = '1'. We can't place a smaller digit (since it would have to be 0, which is not allowed as the first digit). So we must place '1'. Mark '1' as seen.
• Position 1 (tens): S[1] = '3'. We can place digits smaller than 3.
  • Try d = 0: '0' is not seen. We form 10_. The last digit has 8 choices (0-9, excluding 1 and 0). Add 8 to count.
  • Try d = 2: '2' is not seen. We form 12_. The last digit has 8 choices. Add 8 to count.
  • Now, we must place '3'. Mark '3' as seen.
• Position 2 (ones): S[2] = '5'. We can place digits smaller than 5.
  • Try d = 0, 2, 4 (1 and 3 are seen). For each, we form 130, 132, 134. These are 3 numbers. Add 3 to count.
• The loop finishes. Since 135 itself has distinct digits, we add 1 for it.
• Total for 3-digit numbers: 8 + 8 + 3 + 1 = 20.

Grand Total: 90 + 20 = 110.

Here is the code for this approach:

class Solution {
    public int countSpecialNumbers(int n) {
        String s = String.valueOf(n);
        int L = s.length();
        int res = 0;

        // Count special numbers with length < L
        for (int d = 1; d < L; d++) {
            res += 9 * permutations(9, d - 1);
        }

        // Count special numbers with length L and <= n
        boolean[] seen = new boolean[10];
        for (int i = 0; i < L; i++) {
            int digit = s.charAt(i) - '0';
            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {
                if (!seen[d]) {
                    res += permutations(10 - (i + 1), L - 1 - i);
                }
            }
            if (seen[digit]) {
                return res; // Duplicate digit found in n's prefix
            }
            seen[digit] = true;
        }

        // If we reach here, n itself is a special number
        res++;
        return res;
    }

    // Calculates P(m, n) = m! / (m-n)!
    private int permutations(int m, int n) {
        if (n > m) return 0;
        int res = 1;
        for (int i = 0; i < n; i++) {
            res *= (m - i);
        }
        return res;
    }
}