Check if Number Has Equal Digit Count and Digit Value

Difficulty: Easy | Acceptance: 73.20% | Paid: No Topics: Hash Table, String, Counting

You are given a 0-indexed string num of length n consisting of digits.

Return true if for every index i, the digit at index i of num (i.e., num[i]) equals the count of occurrences of digit i in num.

Otherwise return false.

• Examples
• Constraints
• Approach 1: Frequency Array
• Approach 2: Hash Map
• Approach 3: Brute Force

Examples

Example 1:

Input: num = "1210"
Output: true
Explanation:
num[0] = '1'. The digit 0 occurs 1 time in num.
num[1] = '2'. The digit 1 occurs 2 times in num.
num[2] = '1'. The digit 2 occurs 1 time in num.
num[3] = '0'. The digit 3 occurs 0 times in num.
The condition holds true for every index in "1210", so return true.

Example 2:

Input: num = "030"
Output: false
Explanation:
num[0] = '0'. The digit 0 occurs 2 times in num.
num[1] = '3'. The digit 1 occurs 0 times in num.
num[2] = '0'. The digit 2 occurs 0 times in num.
The indices 1 and 2 do not hold the condition, so return false.

Constraints

n == num.length
1 <= n <= 10
num consists of digits.

Approach 1: Frequency Array

Intuition Since the input string consists only of digits (0-9), we can use a fixed-size array of length 10 to count the frequency of each digit. We then iterate through the string to verify if the count matches the digit at each index.

Steps

• Initialize an integer array count of size 10 with all zeros.
• Iterate through the string num. For each character, convert it to an integer and increment the corresponding index in the count array.
• Iterate through the string num again using an index i. Convert the character at i to an integer val.
• Check if count[i] is equal to val. If not, return false.
• If the loop completes without returning false, return true.

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

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string twice.
• Space: O(1), as the count array size is fixed at 10 regardless of input size.
• Notes: This is the most efficient approach for this specific problem due to the limited range of digits.

Approach 2: Hash Map

Intuition We can use a hash map (or dictionary) to store the frequency of each digit found in the string. This is functionally similar to the frequency array but uses a dynamic data structure.

Steps

• Create an empty hash map.
• Iterate through the string num. For each character, update its count in the hash map.
• Iterate through the string num again with index i. Convert the character at i to an integer val.
• Check if the hash map contains key i and if its value equals val. If i is not in the map, the count is implicitly 0.
• If any check fails, return false. Otherwise, return true.

class Solution:
    def digitCount(self, num: str) -> bool:
        freq = {}
        for c in num:
            freq[c] = freq.get(c, 0) + 1
        for i, c in enumerate(num):
            if freq.get(str(i), 0) != int(c):
                return False
        return True

Complexity

• Time: O(n), where n is the length of the string.
• Space: O(1), because the map will store at most 10 entries (digits 0-9).
• Notes: Slightly higher constant overhead than the array approach due to hashing, but logically equivalent.

Approach 3: Brute Force

Intuition For each index i in the string, we can manually count how many times the digit i appears in the entire string and compare it with the value at num[i].

Steps

• Iterate through the string num with index i.
• Initialize a counter to 0.
• Iterate through the string num again with an inner loop.
• If the character in the inner loop equals the string representation of i, increment the counter.
• After the inner loop, compare the counter with the integer value of num[i].
• If they are not equal, return false.
• If the outer loop finishes, return true.

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

Complexity

• Time: O(n²), where n is the length of the string. For each index, we traverse the whole string.
• Space: O(1), no extra space is used apart from variables.
• Notes: Given the constraint n <= 10, this approach is perfectly acceptable and runs very fast in practice, though it scales poorly for larger n.