1941. Check if All Characters Have Equal Number of Occurrences
Problem Description
The problem requires us to determine if a given string s
is a "good" string. A string is considered "good" if every character that appears in the string occurs with the same frequency. That means, each character must appear the same number of times as every other character in the string. For example, the string "aabb" is good because both 'a' and 'b' appear twice. On the other hand, the string "aabc" is not good because the frequency of 'a' is 2, the frequency of 'b' is 1, and the frequency of 'c' is 1. Our function must return true
if the string is good, or false
otherwise.
Intuition
To solve this problem, we need to count the occurrences of each character in the string. A Python dictionary can be used to map each character to the number of times it appears in the string. To facilitate this, we use the Counter
class from Python's collections
module, which automatically creates a dictionary where the keys are the characters from the string and the values are the counts for those characters.
Once we have the counts, the next step is to check if all the counts are the same. To do this, we can convert the dictionary values (the counts) to a set and check the size of the set. A set is a collection of unique items; therefore, if all counts are the same, the set will contain only one element. That's why we check if the length of the set created from cnt.values()
is 1. If so, all characters in the string have the same count, and we return true
. Otherwise, we return false
.
Solution Approach
The solution utilizes a counter and a set to solve the problem efficiently. Here is a step-by-step explanation of the algorithm, utilizing the Python collections.Counter
and Python set
:
-
Initialize Counter: The
Counter
class from Python'scollections
module is used to create a counter object. When theCounter
is instantiated with a strings
, it creates a dictionary-like object. Each key in this object is a unique character from the string, and the corresponding value is the number of times that character appears.cnt = Counter(s)
-
Create a Set of Occurrences: We then use the
values()
method of theCounter
object to get a list of all the frequencies of characters in the string. These values are then turned into a set to eliminate duplicate counts.set(cnt.values())
If all characters occur with the same frequency, this set will only contain one element (that frequency).
-
Compare Set Size: To determine if the string is good, we check the size of the set. If its size is exactly one, this means that all characters in the string occurred an equal number of times.
len(set(cnt.values())) == 1
The expression above will be
True
for a good string andFalse
for a string that is not good. -
Return Result: The result of the comparison mentioned in step 3 is the output of the method
areOccurrencesEqual
. This method returnsTrue
if the string is good andFalse
otherwise.return len(set(cnt.values())) == 1
The Counter
is a hash table-based data structure, and it helps us count the frequency of each character in O(n)
time complexity, with n
being the length of the string. The set conversion and length checking are O(k)
operations where k
is the number of unique characters in the string, which is at most the length of the string and in practice often much less. Therefore, the overall time complexity of the algorithm is O(n)
and is pretty efficient.
The solution elegantly uses the properties of the Python Counter
and set
to determine the "goodness" of the string in a concise and readable manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example to illustrate how it works. Suppose we have the string s = "ccaaabbb"
. We want to determine if this string is "good" according to the problem description.
-
Initialize Counter: First, we create a counter from the string:
from collections import Counter cnt = Counter("ccaaabbb")
The
Counter
objectcnt
will look like this:{'c': 3, 'a': 3, 'b': 3}
. Each key is a unique character, and each value is the number of times that character appears in the string. -
Create a Set of Occurrences: We extract the frequencies of each character and create a set:
frequencies = set(cnt.values())
For our example, the set of frequencies will be
{3}
because each character ('c', 'a', and 'b') appears three times in the string. -
Compare Set Size: Now we check if the size of this set is exactly 1:
is_good_string = len(frequencies) == 1
Since
len({3})
is indeed 1,is_good_string
will beTrue
. -
Return Result: Lastly, we output the result. Since
is_good_string
isTrue
, our methodareOccurrencesEqual
would returnTrue
for the string "ccaaabbb".
Following the above steps, we have determined that "ccaaabbb" is a "good" string according to the given definition because every character in the string has the same frequency of 3. Thus, when the areOccurrencesEqual
function is applied to "ccaaabbb", it returns True
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def areOccurrencesEqual(self, s: str) -> bool:
5 # Create a counter to store the frequency of each character in the string
6 char_count = Counter(s)
7
8 # Get a set of all the frequency values from the counter
9 unique_frequencies = set(char_count.values())
10
11 # Check if all characters have the same frequency, which means
12 # there should only be one unique frequency in the set.
13 # Return True if yes, otherwise return False.
14 return len(unique_frequencies) == 1
15
1class Solution {
2 public boolean areOccurrencesEqual(String s) {
3 // Create an array to hold the count of each letter in the string
4 int[] letterCounts = new int[26];
5
6 // Iterate over the characters in the string and increment the count
7 // for each character in the letterCounts array
8 for (int i = 0; i < s.length(); i++) {
9 letterCounts[s.charAt(i) - 'a']++;
10 }
11
12 // Variable to keep track of the count of the first character
13 int targetCount = 0;
14
15 // Iterate over the counts of each letter
16 for (int count : letterCounts) {
17 // If the count is positive (i.e., the letter is present in the string)
18 if (count > 0) {
19 // If it's the first non-zero count we've seen, set it as the target count
20 if (targetCount == 0) {
21 targetCount = count;
22 } else if (targetCount != count) {
23 // If the current count doesn't match the target count,
24 // not all characters occur the same number of times
25 return false;
26 }
27 }
28 }
29
30 // If we've gotten through the entire letterCounts array and all counts are equal,
31 // return true (all characters occur the same number of times)
32 return true;
33 }
34}
35
1#include <string>
2using namespace std;
3
4class Solution {
5public:
6 bool areOccurrencesEqual(string s) {
7 // Initialize a count array for all 26 letters to 0
8 int letterCount[26] = {0};
9
10 // Count the occurrence of each letter in the string
11 for (char& c : s) {
12 ++letterCount[c - 'a']; // Increment the count for the appropriate letter
13 }
14
15 // The 'occurrenceValue' will hold the number of times a letter should occur
16 int occurrenceValue = 0;
17 // Loop through the count array to determine if all non-zero counts are equal
18 for (int count : letterCount) {
19 if (count) { // If the current letter has occurred at least once
20 if (occurrenceValue == 0) { // If it's the first non-zero count encountered
21 occurrenceValue = count; // Set the 'occurrenceValue' to this count
22 } else if (occurrenceValue != count) { // If the current count doesn't match the 'occurrenceValue'
23 return false; // Not all occurrences are equal, return false
24 }
25 }
26 }
27
28 return true; // All non-zero occurrences are equal, return true
29 }
30};
31
1function areOccurrencesEqual(inputString: string): boolean {
2 // Initialize a count array of length 26 to store the occurrence of each alphabet letter,
3 // corresponding to the lowercase English alphabet letters a-z.
4 const charCounts: number[] = new Array(26).fill(0);
5
6 // Iterate over each character in the input string.
7 for (const char of inputString) {
8 // Increment the count for this character in the charCounts array.
9 // The character code of the current character minus the character code of 'a'
10 // gives the index in the array.
11 charCounts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
12 }
13
14 // Find the first non-zero count in the array to establish a reference count.
15 const referenceCount = charCounts.find(count => count > 0);
16
17 // Return true if every count in the array is either zero (unused character)
18 // or equal to the referenceCount found above. This means all used characters occur
19 // the same number of times in the input string.
20 // If there's any count that is different from referenceCount (and not zero), return false.
21 return charCounts.every(count => count === 0 || count === referenceCount);
22}
23
Time and Space Complexity
The time complexity of the provided code is O(n)
, where n
represents the length of string s
. This is because creating the counter object cnt
requires iterating over all characters in the string once, which is a linear operation.
The space complexity is also O(n)
for the counter object cnt
, which stores a count for each unique character in the string. In the worst case, if all characters are unique, the space required to store the counts is proportional to the number of characters in the string.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!