1941. Check if All Characters Have Equal Number of Occurrences
SourceBiweekly Contest 57 Q1DifficultyEasyRating1242
Description
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.
Solutions
Solution 1: Counting
Thinking
We only need all letter frequencies equal. After counting, the set of frequencies should be a singleton.
One pass over lowercase letters suffices.
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\).
Next, we traverse each value in \(\textit{cnt}\) and check if all non-zero values are equal.
The time complexity is \(O(n)\), and the space complexity is \(O(|\Sigma|)\), where \(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\).
1 2 3 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |