Check if All Characters Have Equal Number of Occurrences

Check if All Characters Have Equal Number of Occurrences

What is this problem about?

The "Check if All Characters Have Equal Number of Occurrences interview question" is a frequency validation task. You are given a string s. You need to determine if all characters that appear in the string have the exact same frequency. For example, in the string "abacaba", the frequencies are different, but in "aabb", every character appears exactly twice.

Why is this asked in interviews?

Companies like Amazon and Google use the "Check if All Characters Have Equal Number of Occurrences coding problem" to test basic knowledge of "Hash Table interview pattern" and frequency counting. It evaluates a candidate's ability to process a string, store character counts efficiently, and then perform a consistency check on those counts. It’s a foundational string processing exercise.

Algorithmic pattern used

This problem follows the Frequency Counting and Validation pattern.

1. Count: Iterate through the string and store the count of each character in a hash map (or a fixed-size array of 26 if the string only contains lowercase letters).
2. Retrieve Baseline: Take the count of the first character encountered.
3. Compare: Iterate through all other unique characters in your map/array and check if their counts match the baseline.
4. Result: If all match, return true; otherwise, return false.

Example explanation

String: "abacba"

1. Counts: a: 3, b: 2, c: 1.
2. Baseline (from 'a'): 3.
3. Check 'b': $2 eq 3$. Result: False. String: "aaabbbccc"
4. Counts: a: 3, b: 3, c: 3.
5. Baseline: 3.
6. All other counts are 3. Result: True.

Common mistakes candidates make

• Inefficient Validation: Using a nested loop to count each character's occurrence, resulting in $O(N^2)$. A hash map approach is $O(N)$.
• Comparing to 0: Forgetting that if using an array of size 26, characters that don't appear in the string will have a count of 0 and should be ignored during the validation phase.
• Empty Map: Not handling the case where the string might be empty (though usually constraints prevent this).

Interview preparation tip

Always remember that for problems involving character counts of a fixed alphabet (like a-z), an array of size 26 is often faster and uses less memory than a general-purpose Hash Map. This is a classic "Array interview pattern" optimization.