Count Numbers With Unique Digits II - Video Solutions

Problem Overview: Given two integers a and b, count how many numbers in the inclusive range [a, b] contain only unique digits. A number is valid if no digit repeats inside its decimal representation.

Approach 1: Direct Enumeration with Hash Set (O(n * d) time, O(d) space)

The straightforward approach iterates through every number from a to b. For each number, convert it to digits and track seen digits using a set or boolean array. If a digit repeats, the number is invalid; otherwise increment the count. This solution relies on simple Hash Table style membership checks for duplicate detection. The digit length d is at most 10, so validation per number is cheap. However, the runtime becomes slow when the range size grows large because every number must be inspected.

Approach 2: State Compression + Digit DP (O(d * 2^10 * 10) time, O(d * 2^10) space)

The optimal approach counts valid numbers without enumerating the entire range. Use digit dynamic programming to build numbers digit by digit while tracking which digits are already used. A 10‑bit mask represents used digits; bit i indicates whether digit i has appeared. The DP state typically includes the current index, the mask, and a tight flag indicating whether the prefix is still constrained by the upper bound. Each transition tries digits 0–9 that are not yet set in the mask. This technique falls under Dynamic Programming and leverages bitmask state compression from Math and combinatorics.

To handle ranges, compute count(b) and subtract count(a - 1). The DP effectively explores only digit combinations, not every integer. Since the mask has 2^10 possibilities and digit length is small (≤10), the complexity stays tiny and independent of the numeric range size.

Recommended for interviews: Start with the enumeration idea to show you understand the constraint (checking repeated digits). Interviewers usually expect the digit DP optimization because it scales to very large ranges. Implementing the bitmask state and tight constraint demonstrates strong understanding of digit-based DP patterns commonly used in counting problems.