LeetCode 1941 - Check if All Characters Have Equal Number of Occurrences

The problem asks us to determine whether a given string s is good, meaning that all characters that appear in the string occur the same number of times.

leetcodeeasyhash-tablestringcounting

LeetCode Problem 1941

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to determine whether a given string s is good, meaning that all characters that appear in the string occur the same number of times. In other words, if you count the frequency of each distinct character, those frequencies should be identical for the string to be considered good.

The input is a string of length between 1 and 1000, consisting solely of lowercase English letters. The output is a boolean: true if the string is good and false otherwise.

Key observations include that a string of length 1 is trivially good since there is only one character, and a string with all identical characters is also good. Edge cases that could trip a naive solution include strings with only one unique character, strings where one character differs in frequency by 1, or strings with all characters appearing exactly once. The constraints tell us the input size is small enough to allow linear scans and hash-based counting without efficiency issues.

Approaches

A brute-force approach would iterate through every unique character, count its occurrences by scanning the entire string each time, and then compare all counts. While this would produce the correct result, it would require O(n * k) time, where n is the string length and k is the number of distinct characters. Given n up to 1000, this approach is feasible but unnecessarily inefficient.

The optimal approach leverages a hash map (dictionary in Python, map in Go) to count the occurrences of each character in a single pass. Once all counts are collected, we simply check whether all frequency values are equal. This reduces the time complexity to O(n) and keeps the space complexity at O(k), where k is at most 26 since we only have lowercase English letters. The key insight is that we can efficiently summarize all character frequencies with a single data structure and then check equality in a straightforward way.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(1) Count each character separately with repeated scans
Optimal O(n) O(k) Single pass frequency count using a hash map and check equality

Algorithm Walkthrough

  1. Initialize an empty hash map (dictionary in Python, map in Go) to store the frequency of each character in the string.
  2. Iterate through each character in the string, incrementing its count in the hash map. This ensures every character's total occurrences are recorded.
  3. Extract the set of values (frequencies) from the hash map. Using a set allows us to immediately detect whether all frequencies are identical.
  4. If the length of the set is 1, it means all characters have the same frequency, so return true. Otherwise, return false.

Why it works: The algorithm works because it counts all occurrences in a single pass, ensuring accurate frequency tallies, and then verifies equality among these frequencies. Using a set to store the frequencies guarantees that any discrepancy among counts is detected.

Python Solution

class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        # Step 1: Count occurrences of each character
        freq = {}
        for char in s:
            if char in freq:
                freq[char] += 1
            else:
                freq[char] = 1
        
        # Step 2: Check if all frequencies are the same
        return len(set(freq.values())) == 1

The implementation creates a dictionary to store counts. Each character increments its count if seen, or is initialized to 1 otherwise. After counting, we convert the frequency values to a set. If all counts are equal, the set will have length 1. This aligns directly with the algorithm steps described above.

Go Solution

func areOccurrencesEqual(s string) bool {
    freq := make(map[rune]int)
    
    // Count occurrences of each character
    for _, char := range s {
        freq[char]++
    }
    
    // Check if all frequencies are the same
    var count int
    first := true
    for _, v := range freq {
        if first {
            count = v
            first = false
        } else if v != count {
            return false
        }
    }
    return true
}

In Go, we use a map from rune to int to count frequencies. We iterate over the map values and compare each frequency to the first one. This avoids converting to a set, which is less idiomatic in Go. The approach guarantees the same correctness as Python.

Worked Examples

Example 1: s = "abacbc"

Step freq dictionary freq set Decision
Scan 'a' {'a':1} - -
Scan 'b' {'a':1,'b':1} - -
Scan 'a' {'a':2,'b':1} - -
Scan 'c' {'a':2,'b':1,'c':1} - -
Scan 'b' {'a':2,'b':2,'c':1} - -
Scan 'c' {'a':2,'b':2,'c':2} {2} All equal, return true

Example 2: s = "aaabb"

Step freq dictionary freq set Decision
Scan 'a' {'a':1} - -
Scan 'a' {'a':2} - -
Scan 'a' {'a':3} - -
Scan 'b' {'a':3,'b':1} - -
Scan 'b' {'a':3,'b':2} {2,3} Not equal, return false

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over the string once to count frequencies, and once over at most 26 values to check equality
Space O(k) The frequency map stores up to 26 entries for lowercase English letters

The complexity is linear in the string length, and space usage is minimal due to the limited alphabet. This ensures excellent performance even at the maximum input length.

Test Cases

# Provided examples
assert Solution().areOccurrencesEqual("abacbc") == True  # all counts are 2
assert Solution().areOccurrencesEqual("aaabb") == False  # counts differ

# Edge cases
assert Solution().areOccurrencesEqual("a") == True  # single character
assert Solution().areOccurrencesEqual("zzzz") == True  # all same character
assert Solution().areOccurrencesEqual("abc") == True  # all appear once
assert Solution().areOccurrencesEqual("aabbccdde") == False  # one character differs

# Larger inputs
assert Solution().areOccurrencesEqual("abcdefghijklmnopqrstuvwxyz"*10) == True  # repeated pattern
assert Solution().areOccurrencesEqual("aaabbbcccdddde") == False  # last char differs by 1
Test Why
"abacbc" Typical good string with multiple characters
"aaabb" Typical bad string with differing counts
"a" Single character string
"zzzz" All characters identical
"abc" Each character appears once
"aabbccdde" One character differs
"abcdefghijklmnopqrstuvwxyz"*10 Larger repeated pattern, all equal counts
"aaabbbcccdddde" Last character differs, edge case for small mismatch

Edge Cases

Single character string: A string like "a" is trivially good because there is only one character, so all characters have the same frequency of 1. The algorithm correctly returns true as the set of frequencies has length 1.

All characters identical: For a string like "zzzz", all characters are the same. The frequency dictionary has only one key with the correct count. The algorithm correctly detects the single frequency and returns true.

One character differs: A string like "aaabbbcccdddde" includes one character that has a frequency differing from the others. This tests whether the algorithm properly identifies the discrepancy. The frequency set will have more than one value, and the algorithm correctly returns false.

This approach robustly handles all these edge cases without additional special handling, thanks to the generality of counting frequencies and checking for equality.