Solution Explanation: Check if All Characters Have Equal Number of Occurrences

The problem asks to determine if all characters in a given string have the same frequency of occurrence. The most efficient approach uses a hash table (or an array in this case, since we're dealing with lowercase English letters) to count character occurrences, followed by a check for frequency equality.

Approach

1. Character Counting: We iterate through the input string s. For each character, we increment its count in a frequency array (cnt). Since we're dealing with lowercase English letters, an array of size 26 is sufficient. cnt[i] will store the count of the character corresponding to 'a' + i.

2. Frequency Check: We iterate through the cnt array.

   • We skip characters with zero occurrences (they don't affect the outcome).
   • If we find a non-zero count that differs from the previously encountered non-zero count (v), it means the frequencies are not equal, and we return false.
   • Otherwise, we update v to the current non-zero count.

3. Return True: If the loop completes without finding unequal frequencies, it means all characters with non-zero occurrences have the same frequency, and we return true.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string s. This is because we iterate through the string once to count character frequencies and then iterate through the cnt array (which has a constant size of 26).

• Space Complexity: O(1). The space used by the cnt array is constant (26 elements), regardless of the input string's length.

Code Implementation in Multiple Languages

The following code snippets implement the approach described above in several programming languages:

Python:

from collections import Counter
 
class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        return len(set(Counter(s).values())) == 1

This Python solution leverages the Counter object from the collections module for efficient character counting. It then checks if the set of counts contains only one unique value.

Java:

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

This Java solution uses an integer array cnt for character counting and efficiently checks for frequency equality.

C++:

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector<int> cnt(26, 0);
        for (char c : s) {
            cnt[c - 'a']++;
        }
        int firstNonZero = -1;
        for (int count : cnt) {
            if (count > 0) {
                if (firstNonZero == -1) {
                    firstNonZero = count;
                } else if (count != firstNonZero) {
                    return false;
                }
            }
        }
        return true;
    }
};

The C++ solution is similar to the Java version, using a vector for character counts.

(Other languages like Go, TypeScript, and PHP would follow a similar structure, using appropriate data structures for character counting and frequency checking.)

This detailed explanation, along with the code examples in multiple languages, provides a comprehensive understanding of how to solve this problem efficiently.