Jobs

Interviews

Discussions

Check if All Characters Have Equal Number of Occurrences #2 Most Asked

Easy

Bolt

1 view

Topics:

ArraysStrings

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 <= 1000
s consists of lowercase English letters.

Try coding it in LeetCode

Check if All Characters Have Equal Number of Occurrences #2 Most Asked

Easy

Bolt

1 view

Topics:

ArraysStrings

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 <= 1000
s consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the character set of the input string? For example, is it limited to lowercase English letters, or can it include uppercase letters, numbers, and special symbols? How should I handle case-sensitivity, for instance, should 'a' and 'A' be treated as the same character?
What are the constraints on the length of the string `s`? Can it be very large?
What should be the expected output for an empty string `s`? Should it return true because the condition vacuously holds, or false?
Does the string contain only ASCII characters, or can it include multi-byte Unicode characters? This might affect how I iterate through the characters and store their counts.
Are there any characters that should be ignored, such as whitespace or punctuation?

Brute Force Solution

Approach

To see if every letter appears the same number of times, we first need to count how many times each unique letter shows up. Then, we can simply compare the count of the first letter to the count of every other letter to see if they are all the same.

Here's how the algorithm would work step-by-step:

First, get a list of all the unique letters present in the text.
Pick the very first unique letter from your list.
Count how many times this first letter appears in the original text. This count will be our reference number.
Now, go through the rest of the unique letters in your list, one by one.
For each of these other letters, count how many times it appears in the original text.
Compare this new count to our reference number.
If you ever find a letter whose count does not match the reference number, you can stop and say the counts are not all equal.
If you check every single unique letter and all of their counts match the reference number, then you can confidently say that all letters appear an equal number of times.

Code Implementation

def are_occurrences_equal(input_string):
    if not input_string:
        return True

    unique_characters = list(set(input_string))

    # Pick the first character's count as the reference to compare all others against.

    first_character = unique_characters[0]
    reference_occurrence_count = input_string.count(first_character)

    # Iterate through the rest of the unique characters to check their counts.

    for character_index in range(1, len(unique_characters)):
        current_character = unique_characters[character_index]
        current_character_count = input_string.count(current_character)

        # If any character count differs, the condition is not met, so we can exit early.

        if current_character_count != reference_occurrence_count:
            return False

    # If all character counts matched the reference count, the condition is met.

    return True

Big(O) Analysis

Time Complexity

O(n * k) – Let n be the length of the input string and k be the number of unique characters. Step 1, finding all unique characters, involves iterating through the string once, which is proportional to n. The main cost comes from the subsequent steps where, for each of the k unique characters, we must iterate through the entire original string of length n to count its occurrences. This counting process is repeated for up to k unique characters. Therefore, the total operations are driven by iterating through the string n times for each of the k unique characters, leading to a time complexity of O(n * k).

Space Complexity

O(K) – The algorithm requires storing a list of all unique letters from the input text. If the input string has a length of N, and the number of unique characters is K, this list will hold K elements. The space used by this list of unique letters is therefore proportional to the number of unique characters, K. Because K is at most the size of the character set (e.g., 26 for lowercase English letters), this can also be considered constant space, O(1), as it does not grow with the length of the input string N.

Optimal Solution

Approach

The core idea is to first count how many times each unique character appears in the text. Then, we simply check if all those counts are the same number.

Here's how the algorithm would work step-by-step:

First, go through the text and tally up the occurrences for every distinct character. For example, in 'aabbc', 'a' appears twice, 'b' appears twice, and 'c' appears once.
Take note of the count of the very first character you see. This count becomes our reference number.
Now, look at the counts for all the other unique characters.
Compare each of these counts to the reference number you established in the previous step.
If any character's count is different from that reference number, you know right away that not all characters appear an equal number of times.
If you check all the unique characters and find that every single one has a count matching the reference number, then you've confirmed they all occur equally.

Code Implementation

def are_occurrences_equal(input_string):
    character_to_count_map = {}

    # Step 1: Tally up the occurrences for every distinct character.
    for character in input_string:
        character_to_count_map[character] = character_to_count_map.get(character, 0) + 1

    # Step 2: Establish a reference count from the first character's frequency.
    # This is the target value that all other character counts must match.
    reference_occurrence_count = character_to_count_map[input_string[0]]

    # Step 4 & 5: Compare each character's count to the reference number.
    # If any count differs, we can immediately conclude the condition is not met.
    for character_count in character_to_count_map.values():
        if character_count != reference_occurrence_count:
            return False

    # Step 6: If all counts match the reference, the condition is met.
    return True

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two main sequential operations on the input string of length n. First, we iterate through the string once to build a frequency map of characters, which takes O(n) time. Second, we iterate through the unique character counts in our map to ensure they are all equal, which in the worst case involves checking every unique character once. Since the number of unique characters cannot exceed n, this second step is also bounded by O(n), resulting in a total time complexity of O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The space complexity is constant because the number of possible characters is finite and does not depend on the input string's length, N. The algorithm requires a data structure, like a hash map or an array of a fixed size (e.g., 26 for lowercase English letters), to store the frequency counts of each character. Since the size of this data structure is capped by the constant number of unique characters in the character set, the space used is O(1).

Edge Cases

Case	How to Handle
Empty string	The solution should return true as the condition of all appearing characters having the same frequency is vacuously met.
Null or undefined input string	The code should handle this gracefully, typically by throwing an error or returning false depending on the requirements.
String with a single character	This is a base case that should return true, as there is only one character type with a single frequency.
String with all identical characters	The solution correctly returns true because only one character type exists, so there's only one frequency to compare.
String with only one of each character	This case should return true since every character appears exactly once, making all frequencies equal to 1.
String with different character casings, e.g., 'aA'	The solution must treat uppercase and lowercase letters as distinct characters unless the problem specifies otherwise.
String containing non-alphanumeric characters like spaces, punctuation, or symbols	These characters should be counted just like letters, each contributing to their own frequency count.
Very long string approaching memory or time limits	The frequency map approach has a time complexity of O(N) and space complexity of O(K), which scales efficiently for large inputs.

Empty string

How to Handle:

The solution should return true as the condition of all appearing characters having the same frequency is vacuously met.

Null or undefined input string

How to Handle:

The code should handle this gracefully, typically by throwing an error or returning false depending on the requirements.

String with a single character

How to Handle:

This is a base case that should return true, as there is only one character type with a single frequency.

String with all identical characters

How to Handle:

The solution correctly returns true because only one character type exists, so there's only one frequency to compare.

String with only one of each character

How to Handle:

This case should return true since every character appears exactly once, making all frequencies equal to 1.

String with different character casings, e.g., 'aA'

How to Handle:

The solution must treat uppercase and lowercase letters as distinct characters unless the problem specifies otherwise.

String containing non-alphanumeric characters like spaces, punctuation, or symbols

How to Handle:

These characters should be counted just like letters, each contributing to their own frequency count.

Very long string approaching memory or time limits

How to Handle:

The frequency map approach has a time complexity of O(N) and space complexity of O(K), which scales efficiently for large inputs.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the character set of the input string? For example, is it limited to lowercase English letters, or can it include uppercase letters, numbers, and special symbols? How should I handle case-sensitivity, for instance, should 'a' and 'A' be treated as the same character?
What are the constraints on the length of the string `s`? Can it be very large?
What should be the expected output for an empty string `s`? Should it return true because the condition vacuously holds, or false?
Does the string contain only ASCII characters, or can it include multi-byte Unicode characters? This might affect how I iterate through the characters and store their counts.
Are there any characters that should be ignored, such as whitespace or punctuation?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, get a list of all the unique letters present in the text.
Pick the very first unique letter from your list.
Count how many times this first letter appears in the original text. This count will be our reference number.
Now, go through the rest of the unique letters in your list, one by one.
For each of these other letters, count how many times it appears in the original text.
Compare this new count to our reference number.
If you ever find a letter whose count does not match the reference number, you can stop and say the counts are not all equal.
If you check every single unique letter and all of their counts match the reference number, then you can confidently say that all letters appear an equal number of times.

Code Implementation

def are_occurrences_equal(input_string):
    if not input_string:
        return True

    unique_characters = list(set(input_string))

    # Pick the first character's count as the reference to compare all others against.

    first_character = unique_characters[0]
    reference_occurrence_count = input_string.count(first_character)

    # Iterate through the rest of the unique characters to check their counts.

    for character_index in range(1, len(unique_characters)):
        current_character = unique_characters[character_index]
        current_character_count = input_string.count(current_character)

        # If any character count differs, the condition is not met, so we can exit early.

        if current_character_count != reference_occurrence_count:
            return False

    # If all character counts matched the reference count, the condition is met.

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to first count how many times each unique character appears in the text. Then, we simply check if all those counts are the same number.

Here's how the algorithm would work step-by-step:

First, go through the text and tally up the occurrences for every distinct character. For example, in 'aabbc', 'a' appears twice, 'b' appears twice, and 'c' appears once.
Take note of the count of the very first character you see. This count becomes our reference number.
Now, look at the counts for all the other unique characters.
Compare each of these counts to the reference number you established in the previous step.
If any character's count is different from that reference number, you know right away that not all characters appear an equal number of times.
If you check all the unique characters and find that every single one has a count matching the reference number, then you've confirmed they all occur equally.

Code Implementation

def are_occurrences_equal(input_string):
    character_to_count_map = {}

    # Step 1: Tally up the occurrences for every distinct character.
    for character in input_string:
        character_to_count_map[character] = character_to_count_map.get(character, 0) + 1

    # Step 2: Establish a reference count from the first character's frequency.
    # This is the target value that all other character counts must match.
    reference_occurrence_count = character_to_count_map[input_string[0]]

    # Step 4 & 5: Compare each character's count to the reference number.
    # If any count differs, we can immediately conclude the condition is not met.
    for character_count in character_to_count_map.values():
        if character_count != reference_occurrence_count:
            return False

    # Step 6: If all counts match the reference, the condition is met.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	The solution should return true as the condition of all appearing characters having the same frequency is vacuously met.
Null or undefined input string	The code should handle this gracefully, typically by throwing an error or returning false depending on the requirements.
String with a single character	This is a base case that should return true, as there is only one character type with a single frequency.
String with all identical characters	The solution correctly returns true because only one character type exists, so there's only one frequency to compare.
String with only one of each character	This case should return true since every character appears exactly once, making all frequencies equal to 1.
String with different character casings, e.g., 'aA'	The solution must treat uppercase and lowercase letters as distinct characters unless the problem specifies otherwise.
String containing non-alphanumeric characters like spaces, punctuation, or symbols	These characters should be counted just like letters, each contributing to their own frequency count.
Very long string approaching memory or time limits	The frequency map approach has a time complexity of O(N) and space complexity of O(K), which scales efficiently for large inputs.

Empty string

How to Handle:

The solution should return true as the condition of all appearing characters having the same frequency is vacuously met.

Null or undefined input string

How to Handle:

The code should handle this gracefully, typically by throwing an error or returning false depending on the requirements.

String with a single character

How to Handle:

This is a base case that should return true, as there is only one character type with a single frequency.

String with all identical characters

How to Handle:

The solution correctly returns true because only one character type exists, so there's only one frequency to compare.

String with only one of each character

How to Handle:

This case should return true since every character appears exactly once, making all frequencies equal to 1.

String with different character casings, e.g., 'aA'

How to Handle:

The solution must treat uppercase and lowercase letters as distinct characters unless the problem specifies otherwise.

String containing non-alphanumeric characters like spaces, punctuation, or symbols

How to Handle:

These characters should be counted just like letters, each contributing to their own frequency count.

Very long string approaching memory or time limits

How to Handle:

The frequency map approach has a time complexity of O(N) and space complexity of O(K), which scales efficiently for large inputs.

0/0 Bolt questions completed

0/0 completed