LeetCode 2376: Count Special Integers

Explanation

To solve this problem, we need to count the number of special integers in the range [1, n]. A special integer is defined as having all distinct digits. We can iterate through each number in the range and check if it is special by converting it to a string and checking if all its characters are unique. We then increment a counter for each special integer found.

• Algorithm Steps:

  1. Initialize a counter to 0 to keep track of special integers.
  2. Iterate through each number from 1 to n.
  3. For each number, convert it to a string and check if all characters are unique (special).
  4. If the number is special, increment the counter.
  5. Finally, return the counter as the result.

• Time Complexity: O(n * log n) where n is the input number.

• Space Complexity: O(log n) for storing the string representation of each number.

class Solution {
    public int countSpecialIntegers(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isSpecial(i)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean isSpecial(int num) {
        String numStr = String.valueOf(num);
        HashSet<Character> set = new HashSet<>();
        for (char c : numStr.toCharArray()) {
            if (set.contains(c)) {
                return false;
            }
            set.add(c);
        }
        return true;
    }
}