Check if Number Has Equal Digit Count and Digit Value - Solution & Explanation

Problem Overview: You are given a numeric string num. For each index i, the digit at that position represents how many times digit i must appear in the entire string. The task is to check whether the actual frequency of every digit matches the value stored at its corresponding index.

Approach 1: Count Digits with a Frequency Array (O(n) time, O(1) space)

The direct solution counts how often each digit appears, then verifies whether those counts match the values in the string. Iterate once through num and update a frequency array of size 10 where freq[d] stores how many times digit d occurs. Then iterate again through the string: for index i, convert num[i] to an integer and compare it with freq[i]. If any index fails the check, return false. If all positions match, the number satisfies the condition. The array size is constant (digits 0–9), so the space complexity stays O(1). This approach relies on simple counting and works well because the digit range is fixed.

Approach 2: Count and Verify In-place (O(n^2) time, O(1) space)

This version avoids storing a separate frequency structure. For each index i, scan the entire string and count how many times digit i appears. Compare that count directly with num[i]. If any mismatch occurs, return false. Since each position triggers a full scan, the algorithm performs up to n scans of length n, giving O(n^2) time complexity. The advantage is minimal memory usage—no extra arrays or hash table structures. The logic is simple but slower for longer inputs.

Recommended for interviews: The frequency array solution is the expected answer. It demonstrates efficient use of string traversal and constant-size counting structures, achieving linear time with minimal space. Showing the naive repeated-count idea first can demonstrate problem understanding, but interviewers typically want the O(n) counting approach.