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 <= 1000s consists of lowercase English letters.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.
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.
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).
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) beyond input storage, with fixed character counts.
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.
| 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 | — |
| 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. |
LeetCode 1941 Solution ( Check if All Characters Have Equal Number of Occurrences ) • Engineering Digest • 1,970 views views
Watch 9 more video solutions →Practice Check if All Characters Have Equal Number of Occurrences with our built-in code editor and test cases.
Practice on FleetCode