Check if All Characters Have Equal Number of Occurrences

Easy

Google

2 views

Topics:

Strings

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

For example:

s = "abacbc" Output: true Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.
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.

Could you implement a function to determine if a given string is a "good" string according to the defined criteria? What is the time and space complexity of your solution? Are there any edge cases to consider?

Check if All Characters Have Equal Number of Occurrences

Easy

Google

2 views

Topics:

Strings

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

For example:

s = "abacbc" Output: true Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.
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.

Solution

Naive Solution

A brute-force approach involves counting the occurrences of each character in the string and then comparing these counts. If all counts are the same, the string is "good".

Create a dictionary (or hash map) to store character counts.
Iterate through the string, updating the counts in the dictionary.
Extract the counts into a list.
Check if all counts in the list are equal.

Code (Python):

def is_good_string_naive(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    
    if not counts:
        return True

    first_count = list(counts.values())[0]
    for count in counts.values():
        if count != first_count:
            return False
    return True

Time Complexity

O(n), where n is the length of the string.

Space Complexity

O(k), where k is the number of unique characters in the string. In the worst case, k can be equal to n (all unique characters), so it can be O(n).

Optimal Solution

The optimal solution is similar to the naive solution but avoids creating an intermediate list of counts. We can compare each count directly to the first count.

Create a dictionary to store character counts.
Iterate through the string to update the counts.
Check if all counts are equal to the first count encountered.

Code (Python):

def is_good_string_optimal(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1

    if not counts:
        return True

    first_count = None
    for count in counts.values():
        if first_count is None:
            first_count = count
        elif count != first_count:
            return False
    return True

Time Complexity

O(n), where n is the length of the string.

Space Complexity

O(k), where k is the number of unique characters in the string. In the worst case, k can be equal to n, so it can be O(n).

Edge Cases

Empty string: An empty string can be considered a "good" string since there are no characters with different frequencies.
String with one character: A string containing only one character is also a "good" string.
String with all same characters: e.g., "aaaaa" is a good string.
String with different characters and frequencies: e.g., "aabbc" is not a good string.

Solution

Naive Solution

A brute-force approach involves counting the occurrences of each character in the string and then comparing these counts. If all counts are the same, the string is "good".

Create a dictionary (or hash map) to store character counts.
Iterate through the string, updating the counts in the dictionary.
Extract the counts into a list.
Check if all counts in the list are equal.

Code (Python):

def is_good_string_naive(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    
    if not counts:
        return True

    first_count = list(counts.values())[0]
    for count in counts.values():
        if count != first_count:
            return False
    return True

Time Complexity

O(n), where n is the length of the string.

Space Complexity

O(k), where k is the number of unique characters in the string. In the worst case, k can be equal to n (all unique characters), so it can be O(n).

Optimal Solution

The optimal solution is similar to the naive solution but avoids creating an intermediate list of counts. We can compare each count directly to the first count.

Create a dictionary to store character counts.
Iterate through the string to update the counts.
Check if all counts are equal to the first count encountered.

Code (Python):

def is_good_string_optimal(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1

    if not counts:
        return True

    first_count = None
    for count in counts.values():
        if first_count is None:
            first_count = count
        elif count != first_count:
            return False
    return True

Time Complexity

O(n), where n is the length of the string.

Space Complexity

O(k), where k is the number of unique characters in the string. In the worst case, k can be equal to n, so it can be O(n).

Edge Cases

Empty string: An empty string can be considered a "good" string since there are no characters with different frequencies.
String with one character: A string containing only one character is also a "good" string.
String with all same characters: e.g., "aaaaa" is a good string.
String with different characters and frequencies: e.g., "aabbc" is not a good string.