# Check if All Characters Have Equal Number of Occurrences
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-all-characters-have-equal-number-of-occurrences)
Canonical: https://scaleengineer.com/dsa/problems/check-if-all-characters-have-equal-number-of-occurrences
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Bolt](https://scaleengineer.com/companies/bolt)
---
## Problem
Given a string `s`, return `true` _if_ `s` _is a **good** string, or_ `false` _otherwise_.

A string `s` is **good** if **all** the characters that appear in `s` have the **same** number of occurrences (i.e., the same frequency).

**Example 1:**

**Input:** s = "abacbc"
**Output:** true
**Explanation:** The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

**Example 2:**

**Input:** s = "aaabb"
**Output:** false
**Explanation:** The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of lowercase English letters.

# Approaches
## Iterative Counting without a Frequency Map
This approach avoids using an explicit frequency map. It first identifies the unique characters in the string. Then, it calculates the frequency of the first unique character and uses this as the target frequency. Finally, it iterates through the remaining unique characters, calculates their frequencies one by one, and compares them against the target frequency.
**Time:** O(U * N), where N is the length of the string and U is the number of unique characters. We iterate through U unique characters, and for each one, we iterate through the entire string of length N. Since U is at most 26, this is technically O(N), but it involves multiple passes over the string, making it less efficient than single-pass solutions. · **Space:** O(U) to store the set of unique characters. For lowercase English letters, U <= 26, so the space is O(1).
**Pros:** Simple to understand logic.; Doesn't require complex data structures besides a Set.
**Cons:** Inefficient due to repeated scanning of the input string.; The time complexity has a larger constant factor (up to 26 passes) compared to other approaches.
### Explanation
This method works by first finding all the unique characters present in the string. It then picks one of these characters, counts how many times it appears in the original string, and sets this count as the 'target' frequency. After that, it does the same for every other unique character, comparing its frequency to the target. If any character's frequency is different, the string is not 'good', and we can immediately return `false`. If we check all unique characters and find that all their frequencies match the target, the string is 'good', and we return `true`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean areOccurrencesEqual(String s) {
        Set<Character> uniqueChars = new HashSet<>();
        for (char c : s.toCharArray()) {
            uniqueChars.add(c);
        }

        if (uniqueChars.size() <= 1) {
            return true;
        }

        int targetCount = -1;

        for (char uniqueChar : uniqueChars) {
            int currentCount = 0;
            for (char c : s.toCharArray()) {
                if (c == uniqueChar) {
                    currentCount++;
                }
            }

            if (targetCount == -1) {
                targetCount = currentCount;
            } else if (targetCount != currentCount) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Create a `Set` to store the unique characters from the input string `s`. This takes one pass through the string.
2. If the set is empty or contains only one character, the condition is trivially met, so return `true`.
3. Take the first character from the set and calculate its frequency by iterating through the entire string `s`. Store this frequency as `targetCount`.
4. Iterate through the rest of the unique characters in the set.
5. For each character, calculate its frequency by iterating through `s` again.
6. If this new frequency does not match `targetCount`, return `false`.
7. If the loop completes without finding any mismatch, it means all characters have the same frequency. Return `true`.

## Using a HashMap for Frequency Counting
A more efficient approach is to count the frequencies of all characters in a single pass and store them in a hash map. After counting, we can iterate through the frequencies stored in the map to check if they are all equal.
**Time:** O(N), where N is the length of the string. The first loop to build the map takes O(N) time. The second loop to check the frequencies takes O(U) time, where U is the number of unique characters (U <= 26). Thus, the total time complexity is O(N + U), which simplifies to O(N). · **Space:** O(U) to store the hash map. Since the string consists of lowercase English letters, U is at most 26. Therefore, the space complexity is O(1).
**Pros:** Efficient single-pass counting.; General solution that works for any character set.
**Cons:** Slightly more overhead than an array-based approach due to hashing and object creation for map entries.
### Explanation
This approach uses a `HashMap` to efficiently store the frequency of each character. We iterate through the string just once to build this map. For example, for the string `"abacbc"`, the map would become `{a=2, b=2, c=2}`. Once the map is built, we need to check if all the frequency values are the same. We can do this by getting the frequency of the first entry, storing it as a reference, and then iterating through the rest of the frequencies in the map to ensure they all match the reference value. If a mismatch is found, we return `false`. If the entire map is checked without a mismatch, we return `true`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean areOccurrencesEqual(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int frequency = -1;
        for (int count : counts.values()) {
            if (frequency == -1) {
                frequency = count;
            } else if (frequency != count) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Initialize a `HashMap<Character, Integer>` to store character frequencies.
2. Iterate through the input string `s` once. For each character, increment its count in the hash map.
3. After populating the map, retrieve the frequency of the first character (or any character) in the map. This will be our reference frequency.
4. Iterate through all the frequency values in the hash map.
5. Compare each frequency with the reference frequency. If any frequency is different, return `false`.
6. If the loop completes, it means all characters that appeared in the string have the same frequency. Return `true`.

## Optimized Frequency Counting with an Array
Given that the input string consists only of lowercase English letters, we can optimize the frequency counting process by using a fixed-size array of 26 integers instead of a hash map. This eliminates the overhead of hashing and is generally faster.
**Time:** O(N), where N is the length of the string. We iterate through the string once to populate the array (O(N)) and then iterate through the fixed-size array of 26 elements (O(1)). The total time is dominated by the first pass, making it O(N). · **Space:** O(1). We use an array of a fixed size (26), which does not depend on the input string length.
**Pros:** Most efficient approach in terms of both time and space for the given constraints.; Avoids hashing overhead and object allocations, leading to better performance.
**Cons:** This solution is specific to the character set (lowercase English letters). It would need modification for a different or larger character set.
### Explanation
This is the most optimized approach for this problem's constraints. Since we know the characters are limited to the 26 lowercase English letters, we can use a simple integer array of size 26 as a direct-access frequency map. The index `0` of the array stores the count of 'a', index `1` for 'b', and so on. We can calculate the index for any character `c` with the expression `c - 'a'`. We first pass through the string to populate this array. Then, we make a second pass through the frequency array itself. We find the first non-zero frequency and store it as our target. Then we continue iterating, and if we find any other non-zero frequency that doesn't match our target, we return `false`. If we finish checking the array, it means all characters have equal occurrences.

```java
class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        int targetFreq = 0;
        for (int count : counts) {
            if (count == 0) {
                continue; // Skip characters that didn't appear
            }
            if (targetFreq == 0) {
                // This is the first character frequency we've found
                targetFreq = count;
            } else if (count != targetFreq) {
                // Found a different frequency
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
1. Initialize an integer array `freq` of size 26 with all elements as 0. Each index `i` in the array will correspond to the character `'a' + i`.
2. Iterate through the input string `s`. For each character `c`, increment the corresponding counter in the array: `freq[c - 'a']++`.
3. After counting, find the frequency of the first character that appears in the string. Initialize a variable `targetFreq = 0`.
4. Iterate through the `freq` array.
5. Skip any zero counts, as they correspond to characters not present in the string.
6. If `targetFreq` is 0 (meaning this is the first non-zero count we've found), set `targetFreq` to the current count.
7. If the current count is non-zero and not equal to `targetFreq`, return `false`.
8. If the loop finishes, all present characters have the same frequency. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean areOccurrencesEqual(String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    int x = 0;
    for (int v : cnt) {
      if (v > 0) {
        if (x == 0) {
          x = v;
        } else if (x != v) {
          return false;
        }
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool areOccurrencesEqual(string s) {
    int cnt[26]{};
    for (char &c : s) {
      ++cnt[c - 'a'];
    }
    int x = 0;
    for (int &v : cnt) {
      if (v) {
        if (!x) {
          x = v;
        } else if (x != v) {
          return false;
        }
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def areOccurrencesEqual(self, s: str) -> bool: cnt = Counter(s) return len(set(cnt . values())) == 1

```