#1941

Easy

LeetCode Problem Workspace

Check if All Characters Have Equal Number of Occurrences

Check if a string has characters with equal occurrences using hash tables and string manipulation techniques.

Problem Statement

You are given a string s consisting of lowercase English letters. Your task is to determine if the string is a 'good' string, meaning that all characters that appear in s have the same frequency of occurrences.

Return true if the string is good, otherwise return false. A string is good if, for every character in the string that occurs, it occurs the same number of times as the other characters in the string.

Examples

Example 1

Input: s = "abacbc"

Output: true

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

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.

Solution Approach

Count Character Frequencies

Build a dictionary or hash table to store the frequency of each character in the string. This allows us to efficiently track how many times each character appears in the string.

Check Frequency Consistency

Once we have the frequency counts, we can compare all the values in the hash table. If all frequencies are the same, return true; otherwise, return false.

Optimize with Early Exit

During the comparison phase, if we find a mismatch in the frequencies early on, we can immediately return false, optimizing the solution by avoiding further unnecessary checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string, since we are iterating through the string once to build the frequency table and potentially once more to check the frequencies. The space complexity is O(k), where k is the number of unique characters in the string, as we store the frequencies in a hash table.

What Interviewers Usually Probe

The candidate should efficiently build and check the frequency table.
The candidate should consider edge cases like strings with only one type of character or strings with a large number of unique characters.
The candidate should demonstrate an understanding of optimizing with early exits.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the frequency consistency across all characters.
Using inefficient data structures that lead to unnecessary computation or memory usage.
Not handling strings with varying numbers of unique characters correctly.

Follow-up variants

Modify the problem to include case-insensitive comparisons.
Allow the string to contain non-English characters.
Optimize the solution to handle very large strings with more efficient space usage.

FAQ

What is the key pattern for solving the 'Check if All Characters Have Equal Number of Occurrences' problem?

The key pattern for this problem is to use a hash table to count character frequencies, followed by checking if all the frequencies are the same.

How do I know if my solution is optimized for large inputs?

Ensure your solution runs in O(n) time complexity and uses space proportional to the number of unique characters in the string.

What are the common pitfalls when solving this problem?

Common pitfalls include failing to check the consistency of frequencies and using inefficient data structures.

Can I solve this problem without using a hash table?

While it's possible to solve this problem with other methods, using a hash table is the most efficient approach for counting and checking frequencies.

What other problems are similar to 'Check if All Characters Have Equal Number of Occurrences'?

Other similar problems involve frequency counting, such as 'Find the Most Frequent Character' or 'Group Anagrams'.

terminal

Solution

Solution 1: Counting

We use a hash table or an array of length $26$ called $\textit{cnt}$ to record the number of occurrences of each character in the string $s$.

1

2

3

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

Continue Practicing

#1897 redistribute characters to make all strings equal #1876 substrings of size three with distinct characters #2023 number of pairs of strings with concatenation equal to target