LeetCode 2283 - Check if Number Has Equal Digit Count and Digit Value

LeetCode Problem 2283

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

This problem asks us to verify a self-descriptive property of a string of digits. You are given a string num of length n, where each character is a digit between '0' and '9'. The requirement is that for every index i in the string, the digit i must appear exactly num[i] times in the entire string.

In simpler terms, if num[i] = '3', then the digit i should appear exactly three times in the string. If this condition holds for every index, we return true; otherwise, we return false.

The input constraints tell us that 1 <= n <= 10, meaning the string is very short, so even O(n²) solutions are feasible. The string contains only digits, which simplifies counting since we can use an array or hash map of size 10. Important edge cases include strings where counts are zero, strings with repeated digits that violate the self-descriptive property, and strings of length 1.

Approaches

The brute-force approach is straightforward: for each index i in num, count how many times the digit i appears in the string, and compare it to num[i]. If any count does not match, return false. This works because it directly implements the definition of the problem. Given the constraints (n <= 10), this approach is acceptable, but it performs redundant work, recalculating counts for the same digits multiple times.

The optimal approach improves on this by pre-counting the occurrences of all digits in the string using a single pass. Then, we iterate through each index and simply check if the count of the digit i matches num[i]. This reduces repeated counting and makes the logic cleaner. Since the string is very short, the performance gain is minimal in practice, but this approach scales better conceptually.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Count each digit for every index
Optimal	O(n)	O(10) = O(1)	Pre-count digits, then compare counts

Algorithm Walkthrough

1. Initialize an array digit_count of size 10 to store the count of each digit from 0 to 9.
2. Iterate through each character c in the string num. Convert c to an integer d and increment digit_count[d].
3. Iterate through each index i in the range from 0 to n-1. Convert num[i] to an integer expected_count.
4. Check if digit_count[i] equals expected_count. If not, return false immediately.
5. If the loop completes without returning false, all conditions are satisfied, so return true.

Why it works: The algorithm correctly captures the frequency of each digit in a single pass, and the subsequent check ensures that the self-descriptive condition holds for every index. Using a pre-count array guarantees that each digit's occurrence is only computed once, making the check reliable and efficient.

Python Solution

class Solution:
    def digitCount(self, num: str) -> bool:
        n = len(num)
        digit_count = [0] * 10
        
        for c in num:
            digit_count[int(c)] += 1
        
        for i in range(n):
            expected_count = int(num[i])
            if digit_count[i] != expected_count:
                return False
        
        return True

The implementation first creates a digit_count array to store occurrences of each digit. It iterates over the string to fill this array. Then, for each index i, it checks whether the actual count of digit i matches the expected count defined by num[i]. If any mismatch occurs, it returns false; otherwise, it returns true.

Go Solution

func digitCount(num string) bool {
    n := len(num)
    digitCount := make([]int, 10)
    
    for i := 0; i < n; i++ {
        d := int(num[i] - '0')
        digitCount[d]++
    }
    
    for i := 0; i < n; i++ {
        expectedCount := int(num[i] - '0')
        if digitCount[i] != expectedCount {
            return false
        }
    }
    
    return true
}

In Go, we use a slice of length 10 to store counts. We convert each character to an integer by subtracting '0'. The logic otherwise mirrors the Python version, ensuring all digits are counted once and compared to the expected values.

Worked Examples

Example 1: num = "1210"

Index i	num[i]	Digit i count in num	Condition satisfied?
0	1	1	Yes
1	2	2	Yes
2	1	1	Yes
3	0	0	Yes

Return: true

Example 2: num = "030"

Index i	num[i]	Digit i count in num	Condition satisfied?
0	0	2	No
1	3	0	No
2	0	1	No

Return: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count digits and one pass to check counts
Space	O(1)	Array of size 10, constant with respect to input size

Because n is at most 10, both time and space requirements are trivial, but the algorithm scales linearly with n in theory.

Test Cases

# Provided examples
assert Solution().digitCount("1210") == True  # All counts match
assert Solution().digitCount("030") == False  # Counts mismatch

# Boundary cases
assert Solution().digitCount("0") == True  # Single digit 0 occurs 0 times
assert Solution().digitCount("1") == False  # Single digit 1 occurs 1 time, violates index 0
assert Solution().digitCount("22") == False  # Two-digit, counts mismatch

# Maximum length 10, all zeros
assert Solution().digitCount("0000000000") == False  # All digits expected zero, actual counts not zero

# Maximum length 10, valid self-descriptive
assert Solution().digitCount("6210001000") == True  # Each index matches count

Test	Why
"1210"	Valid self-descriptive string
"030"	Invalid counts for multiple indices
"0"	Edge case, single character
"1"	Edge case, single character not matching 0th index
"22"	Two characters, counts mismatch
"0000000000"	All zeros, counts mismatch
"6210001000"	Maximum length, valid self-descriptive

Edge Cases

Single character string: For num of length 1, the only valid string is "0" since the digit at index 0 must occur 0 times. Strings like "1" violate this condition. The algorithm correctly handles this by counting occurrences and checking index 0.

Digits exceeding string length: If a digit's expected count exceeds the length of the string, such as num = "500" (length 3, but index 0 expects 5 occurrences), the algorithm will fail the check naturally because the count of any digit cannot exceed the string length.

All zeros: A string like "0000" might appear tricky. Each index expects 0 occurrences, but digit 0 occurs multiple times. The algorithm correctly counts digit 0 and identifies the mismatch, returning false.

This approach reliably handles all these edge cases by directly counting actual occurrences and comparing to the expected count.