Code Implementation

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        from collections import Counter
        count = Counter(s)
        values = list(count.values())
        return all(v == values[0] for v in values)
      

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        unordered_map<char, int> freq;
        for(char c : s) {
            freq[c]++;
        }
        int count = freq.begin()->second;
        for(auto &[ch, cnt] : freq) {
            if(cnt != count) return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        int count = 0;
        for (int f : freq) {
            if (f != 0) {
                if (count == 0) count = f;
                else if (f != count) return false;
            }
        }
        return true;
    }
}
      

var areOccurrencesEqual = function(s) {
    let freq = {};
    for (let c of s) {
        freq[c] = (freq[c] || 0) + 1;
    }
    let counts = Object.values(freq);
    return counts.every(v => v === counts[0]);
};
      

Problem Description

Given a string s, determine if every character in s appears the same number of times. In other words, check if all unique characters in s have equal frequency of occurrence.

• You may assume s consists only of lowercase English letters.
• Return true if all characters have the same number of occurrences, otherwise return false.
• There is no restriction on character reuse; simply count frequency.

Thought Process

To solve this problem, the first idea is to count how many times each character appears in the string. If all characters appear the same number of times, then every character's count should be equal.

A brute-force way would be to count each character's frequency and then compare every pair of counts. However, this is inefficient and unnecessary. Instead, we can store the frequencies in a map or array, and then check if all the values are the same.

This leads us to an optimized approach: count the frequencies, then check if all frequency values are equal by comparing them to the first one found.

Solution Approach

• Step 1: Traverse the string and count the frequency of each character. This can be done using a hash map (dictionary), array, or similar data structure.
• Step 2: Once all frequencies are collected, extract the frequency values.
• Step 3: Compare all frequency values to the first one. If any value differs, return false.
• Step 4: If all values are equal, return true.

We use a hash map because it allows us to count occurrences in O(1) time per character, and it handles any set of characters efficiently. For languages with fixed small alphabets (like lowercase English letters), an array of length 26 can also be used.

This approach is simple, easy to implement, and runs efficiently for all reasonable input sizes.

Example Walkthrough

Let's consider the example s = "abacbc".

1. Count character frequencies:
   • 'a': 2 times
   • 'b': 2 times
   • 'c': 2 times
2. Extract frequency values: [2, 2, 2]
3. Compare all to the first value (2): all are equal.
4. Return true because all characters have the same number of occurrences.

If the string was "aabbccc", the counts would be [2, 2, 3], and since not all are equal, the function would return false.

Time and Space Complexity

• Brute-force Approach: Counting each character's frequency separately would take O(N^2) time, where N is the length of the string, since you'd scan the string for each unique character.
• Optimized Approach:
  • Time Complexity: O(N) — We traverse the string once to count frequencies, and then at most 26 iterations to check equality.
  • Space Complexity: O(1) — The hash map or array can contain at most 26 entries (for lowercase English letters), so space does not scale with input size.

Summary

The key to this problem is recognizing that a frequency count for each character allows an efficient check for equal occurrence. Using a hash map or array, we can count and compare frequencies in linear time. This approach is both simple and powerful, showing how mapping data structures can elegantly solve counting problems.