Check if All Characters Have Equal Number of Occurrences

Difficulty: Easy | Acceptance: 79.50% | Paid: No Topics: Hash Table, String, Counting

Given a string s, return true if all characters that appear in s appear the same number of times, or false otherwise.

• Examples
• Constraints
• Hash Map Frequency Count
• Fixed Array Counting
• Sorting

Examples

Example 1:

Input: s = "abacbc"
Output: true
Explanation: All characters appear 2 times.

Example 2:

Input: s = "aaabb"
Output: false
Explanation: 'a' appears 3 times, 'b' appears 2 times.

Constraints

1 <= s.length <= 1000
s[i] is a lowercase English letter.

Hash Map Frequency Count

Intuition We can iterate through the string and store the frequency of each character in a hash map. After counting, we simply check if all the frequency values in the map are identical.

Steps

• Initialize an empty hash map.
• Iterate through the string s, incrementing the count for each character in the map.
• Extract the first frequency value from the map to use as a reference.
• Iterate through all frequency values in the map. If any value differs from the reference, return false.
• If the loop completes without finding a difference, return true.

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        counts = {}
        for char in s:
            counts[char] = counts.get(char, 0) + 1
        values = list(counts.values())
        return len(set(values)) == 1

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once and the map once.
• Space: O(1), because the hash map will store at most 26 keys (lowercase English letters).
• Notes: Using a set to check uniqueness of values is a concise way to verify equality in Python.

Fixed Array Counting

Intuition Since the input string consists only of lowercase English letters, we can optimize space and speed by using a fixed-size integer array of length 26 instead of a hash map. This avoids the overhead of hashing.

Steps

• Initialize an integer array counts of size 26 with zeros.
• Iterate through the string s. For each character, calculate its index (e.g., char - 'a') and increment the corresponding value in counts.
• Iterate through the counts array to find the first non-zero value to set as the target frequency.
• Continue iterating through the array. If any non-zero value differs from the target, return false.
• Return true if all non-zero counts match.

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        counts = [0] * 26
        for char in s:
            counts[ord(char) - ord('a')] += 1
        target = -1
        for count in counts:
            if count == 0:
                continue
            if target == -1:
                target = count
            elif count != target:
                return False
        return True

Complexity

• Time: O(n), where n is the length of the string.
• Space: O(1), as the array size is fixed at 26 regardless of input size.
• Notes: This is generally the fastest approach for this specific problem due to cache locality and lack of hashing overhead.

Sorting

Intuition If we sort the string, all identical characters will be adjacent. We can then iterate through the sorted string, counting the length of each “run” of identical characters and comparing these lengths.

Steps

• Convert the string to a character array (or equivalent) and sort it.
• Initialize a counter for the current character frequency.
• Iterate through the sorted string. If the current character matches the previous one, increment the counter.
• If the current character is different, compare the completed counter with the target frequency. If they differ, return false. Otherwise, reset the counter.
• After the loop, perform a final check for the last group of characters.

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        s = sorted(s)
        target = 1
        count = 1
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                if target == 1:
                    target = count
                elif count != target:
                    return False
                count = 1
        return count == target or target == 1

Complexity

• Time: O(n log n), due to the sorting step.
• Space: O(n) or O(log n), depending on the sorting algorithm’s implementation (e.g., Java’s Arrays.sort uses O(n) space for objects, O(log n) for primitives).
• Notes: This approach is less efficient than counting but demonstrates a valid alternative using sorting.