Digit Frequency Score - Solution & Explanation

Problem Overview: You receive a number or digit string and must compute a score derived from how often each digit appears. The task reduces to counting occurrences of digits (0–9) and applying the rule defined in the problem to produce the final score.

Approach 1: Recount Digits for Every Check (Brute Force) (Time: O(n^2), Space: O(1))

One straightforward approach repeatedly scans the string to determine how often each digit appears. For every digit you encounter, iterate through the entire string again and count matches. After collecting these counts, apply the scoring rule (for example comparing highest and lowest frequencies or applying weights). This works but wastes time because the same digits are counted many times. It’s mainly useful to demonstrate the baseline logic before optimizing.

Approach 2: Hash Map Frequency Counting (Time: O(n), Space: O(k))

A better solution stores digit counts while scanning the string once. Use a hash table where the key is the digit and the value is its frequency. Each character is processed with a constant-time hash lookup and increment. Once the pass finishes, iterate through the stored counts and compute the score according to the problem rule. This removes repeated scans and reduces the runtime to linear. This approach uses concepts from hash maps and basic frequency counting.

Approach 3: Fixed-Size Digit Array (Optimal) (Time: O(n), Space: O(1))

Digits are limited to 0–9, so a hash map is unnecessary. Instead, allocate an integer array of size 10 and treat each index as the frequency counter for a digit. Iterate through the string once, convert each character to its numeric value, and increment freq[digit]. After counting, iterate through the 10 slots and compute the score using the stored frequencies. This keeps the algorithm linear while using constant extra memory. The technique relies on simple array indexing and is usually the cleanest implementation.

Recommended for interviews: The fixed-size array counting approach is what interviewers typically expect. The brute-force method shows you understand the underlying task, but the optimal array-based frequency count demonstrates awareness of constraints and efficient use of constant-size structures.