Check if All Characters Have Equal Number of Occurrences - Solution & Explanation
Problem Statement
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 <= 1000sconsists of lowercase English letters.
Approach Overview
Problem Overview: You get a string s. Every character should appear the same number of times. If all characters share an identical frequency, return true; otherwise return false. The task reduces to counting character frequencies and verifying they are equal.
Approach 1: Use a Frequency Dictionary (O(n) time, O(k) space)
The most direct solution counts how many times each character appears using a dictionary or hash map. Iterate through the string once and update the count for each character. After building the frequency map, take the first frequency as a reference and iterate through the remaining counts to ensure they match. Hash lookups and updates run in constant time, so the entire operation is linear in the length of the string. This approach relies on a hash table for fast counting and works efficiently for any string size.
Approach 2: Sort Frequencies (O(n + k log k) time, O(k) space)
Start the same way by counting character occurrences. Store all frequency values in a list and sort the list. If every element in the sorted list is equal to the first element, all characters occur the same number of times. Sorting adds a k log k cost where k is the number of distinct characters, while counting still takes O(n). This approach is slightly less efficient but very easy to reason about because identical frequencies appear consecutively after sorting. The solution still depends on character counting using concepts from counting and string processing.
Recommended for interviews: The frequency dictionary approach is what interviewers expect. It demonstrates that you can model the problem as a counting task and use constant-time hash lookups to achieve O(n) time. The sorting variant is acceptable but slightly less optimal. Showing both indicates you understand tradeoffs between direct frequency comparison and post-processing techniques like sorting.
Approach 1: Use a Frequency Dictionary
This approach leverages a dictionary (or hashmap) to count the occurrences of each character in the string. Once the counts are recorded, we check if all the frequencies are the same.
In this Python solution, we use the collections.Counter class to count the occurrences of each character in the string. After obtaining the frequencies, we convert them into a set, which will remove any duplicates. If all the frequencies are the same, the set will contain only one item, so we check if the length of the set is 1.
Complexity
Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.
Space Complexity: O(1), in terms of the extra space used for the counter and set, assuming a fixed number of possible unique characters (26 for lowercase English letters).
Approach 2: Sort Frequencies
This approach involves counting character frequencies, sorting them, and checking if all sorted values are the same. Although not the most optimal, it's an alternative method to ensure all characters have equal frequency.
Here, we count character occurrences, sort the frequency list, and check the first and last elements since they would differ if any counts were unique.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) beyond input storage, with fixed character counts.
Approach 3: Counting
We use a hash table or an array of length 26 called cnt to record the number of occurrences of each character in the string s.
Next, we traverse each value in cnt and check if all non-zero values are equal.
The time complexity is O(n), and the space complexity is O(|\Sigma|). Here, n is the length of the string s, and \Sigma is the size of the character set. In this problem, the character set consists of lowercase English letters, so |\Sigma|=26.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Use a Frequency Dictionary | Time Complexity: O(n), where n is the length of the string, as we iterate through the string once. |
| Sort Frequencies | Time Complexity: O(n log n) due to sorting. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Dictionary | O(n) | O(k) | General case. Fastest and most common interview solution using hash map counting. |
| Sort Frequencies | O(n + k log k) | O(k) | Useful when you want a simple comparison step after sorting frequency values. |
Video Solution
LeetCode 1941 Solution ( Check if All Characters Have Equal Number of Occurrences ) • Engineering Digest • 2,068 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if All Characters Have Equal Number of Occurrences easy or hard?
Check if All Characters Have Equal Number of Occurrences Python/Java solution
How to solve Check if All Characters Have Equal Number of Occurrences in O(n)?
What is the best approach for Check if All Characters Have Equal Number of Occurrences?
Is Check if All Characters Have Equal Number of Occurrences asked at Google/Amazon/Meta?
What data structure is used in Check if All Characters Have Equal Number of Occurrences?
What is the time complexity of Check if All Characters Have Equal Number of Occurrences?
Ready to solve this problem?
Practice Check if All Characters Have Equal Number of Occurrences with our built-in code editor and test cases.
Practice on FleetCode