# Check if Number Has Equal Digit Count and Digit Value
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-number-has-equal-digit-count-and-digit-value)
Canonical: https://scaleengineer.com/dsa/problems/check-if-number-has-equal-digit-count-and-digit-value
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [PornHub](https://scaleengineer.com/companies/pornhub)
---
## Problem
You are given a **0-indexed** string `num` of length `n` consisting of digits.

Return `true` _if for **every** index_ `i` _in the range_ `0 <= i < n`_, the digit_ `i` _occurs_ `num[i]` _times in_ `num`_, otherwise return_ `false`.

**Example 1:**

**Input:** num = "1210"
**Output:** true
**Explanation:**
num[0] = '1'. The digit 0 occurs once in num.
num[1] = '2'. The digit 1 occurs twice in num.
num[2] = '1'. The digit 2 occurs once in num.
num[3] = '0'. The digit 3 occurs zero 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 should occur zero times, but actually occurs twice in num.
num[1] = '3'. The digit 1 should occur three times, but actually occurs zero times in num.
num[2] = '0'. The digit 2 occurs zero times in num.
The indices 0 and 1 both violate the condition, so return false.

**Constraints:**

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

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem statement into code. It iterates through each index `i` of the string and, for each `i`, it performs another iteration through the entire string to count the occurrences of the digit `i`. It then compares this count with the expected count given by `num[i]`.
**Time:** O(n^2), where `n` is the length of the string `num`. The outer loop runs `n` times, and for each iteration, the inner loop also runs `n` times to count the occurrences. · **Space:** O(1), as we only use a few variables to store the counts and indices, requiring constant extra space.
**Pros:** Simple to understand and implement.; Requires no extra data structures.
**Cons:** Inefficient for larger inputs due to the quadratic time complexity. However, it's acceptable for the given constraints (n <= 10).
### Explanation
The brute-force method involves a straightforward, nested-loop implementation. The outer loop iterates through each possible digit `i` from `0` to `n-1`, where `n` is the length of the string. For each digit `i`, the inner loop traverses the entire string `num` to count how many times `i` actually appears. This `actualCount` is then compared with the `expectedCount`, which is derived from the character `num[i]`.

```java
class Solution {
    public boolean digitCount(String num) {
        int n = num.length();
        for (int i = 0; i < n; i++) {
            // The digit i should appear num[i] times.
            int expectedCount = num.charAt(i) - '0';
            int actualCount = 0;
            
            // Count the actual occurrences of digit i in the string.
            for (int j = 0; j < n; j++) {
                if ((num.charAt(j) - '0') == i) {
                    actualCount++;
                }
            }
            
            // If the counts don't match, return false.
            if (actualCount != expectedCount) {
                return false;
            }
        }
        // If all checks pass, return true.
        return true;
    }
}
```
### Algorithm
*   Iterate through the string `num` with an index `i` from `0` to `n-1`, where `n` is the length of the string.
*   For each index `i`, determine the expected count of the digit `i`. This is the integer value of the character `num[i]`. Let's call it `expectedCount`.
*   Initialize a counter `actualCount` to zero.
*   Start a nested loop to iterate through the string `num` again with an index `j` from `0` to `n-1`.
*   Inside the nested loop, check if the digit at `num[j]` is equal to the digit `i`.
*   If `(num.charAt(j) - '0') == i`, increment `actualCount`.
*   After the nested loop finishes, compare `expectedCount` with `actualCount`.
*   If `expectedCount` is not equal to `actualCount`, the condition is violated, so return `false` immediately.
*   If the outer loop completes without finding any mismatch, it means the condition holds for all indices. Return `true`.

## Single Pass with Frequency Array
A more efficient approach involves pre-calculating the frequency of each digit in the input string. We can use an array of size 10 to store the counts of digits 0 through 9. After a single pass to populate this frequency array, we can then iterate through the string again to check if the condition holds for each index.
**Time:** O(n), where `n` is the length of the string `num`. We perform two separate passes over the string (or related to its length), each taking O(n) time. This results in a linear time complexity. · **Space:** O(1). We use a frequency array of size 10. Since the size of this array is constant and does not depend on the input size `n`, the space complexity is constant.
**Pros:** More efficient with a linear time complexity.; Scales better for larger inputs compared to the brute-force approach.
**Cons:** Requires a small amount of extra space for the frequency array.
### Explanation
This optimized approach avoids the redundant counting of the brute-force method by using a frequency array. It first makes a single pass through the string to count the occurrences of each digit and stores them in an array. Then, it makes a second pass to verify the condition for each index `i` by comparing the value `num[i]` with the pre-calculated count of digit `i`.

```java
class Solution {
    public boolean digitCount(String num) {
        int n = num.length();
        int[] counts = new int[10];
        
        // First pass: count the frequency of each digit in the string.
        for (int i = 0; i < n; i++) {
            int digit = num.charAt(i) - '0';
            counts[digit]++;
        }
        
        // Second pass: check if the condition holds for each index.
        for (int i = 0; i < n; i++) {
            // The digit i should appear num[i] times.
            int expectedCount = num.charAt(i) - '0';
            
            // The actual count of digit i.
            int actualCount = counts[i];
            
            if (actualCount != expectedCount) {
                return false;
            }
        }
        
        return true;
    }
}
```
### Algorithm
*   Create an integer array `counts` of size 10, initialized to all zeros. This array will store the frequency of each digit from 0 to 9.
*   Iterate through the input string `num` once. For each character `c` in `num`:
    *   Convert the character to its integer value: `digit = c - '0'`.
    *   Increment the count for this digit in the frequency array: `counts[digit]++`.
*   After the first loop, `counts[d]` will hold the total number of times digit `d` appears in `num`.
*   Iterate again from `i = 0` to `n-1`, where `n` is the length of `num`.
*   For each index `i`:
    *   Get the expected count from the string: `expectedCount = num.charAt(i) - '0'`.
    *   Get the actual count from our frequency array: `actualCount = counts[i]`.
    *   If `expectedCount` is not equal to `actualCount`, return `false`.
*   If the second loop completes without returning `false`, it means the condition is satisfied for all indices. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean digitCount(String num) {
    int[] cnt = new int[10];
    int n = num.length();
    for (int i = 0; i < n; ++i) {
      ++cnt[num.charAt(i) - '0'];
    }
    for (int i = 0; i < n; ++i) {
      if (cnt[i] != num.charAt(i) - '0') {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool digitCount(string num) {
    int cnt[10]{};
    for (char &c : num) {
      ++cnt[c - '0'];
    }
    for (int i = 0; i < num.size(); ++i) {
      if (cnt[i] != num[i] - '0') {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def digitCount(self, num: str) -> bool: cnt = Counter(num) return all(cnt[str(i)] == int(v) for i, v in enumerate(num))

```