1941. Check if All Characters Have Equal Number of Occurrences

EasyHash TableStringCounting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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:

  1. Initialize Counter: The Counter class from Python's collections module is used to create a counter object. When the Counter is instantiated with a string s, 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.

    1cnt = Counter(s)

  2. Create a Set of Occurrences: We then use the values() method of the Counter 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.

    1set(cnt.values())

    If all characters occur with the same frequency, this set will only contain one element (that frequency).

  3. 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.

    1len(set(cnt.values())) == 1

    The expression above will be True for a good string and False for a string that is not good.

  4. Return Result: The result of the comparison mentioned in step 3 is the output of the method areOccurrencesEqual. This method returns True if the string is good and False otherwise.

    1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example 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.

  1. Initialize Counter: First, we create a counter from the string:

    1from collections import Counter
2cnt = Counter("ccaaabbb")

    The Counter object cnt 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.

  2. Create a Set of Occurrences: We extract the frequencies of each character and create a set:

    1frequencies = 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.

  3. Compare Set Size: Now we check if the size of this set is exactly 1:

    1is_good_string = len(frequencies) == 1

    Since len({3}) is indeed 1, is_good_string will be True.

  4. Return Result: Lastly, we output the result. Since is_good_string is True, our method areOccurrencesEqual would return True 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
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the maximum element can be found in:

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫