Leetcode 1941: Check if All Characters Have Equal Number of Occurrences

Input: A single string s containing lowercase English letters.

Example: s = "abbcaa"

Constraints:

• 1 <= s.length <= 1000

• s consists of lowercase English letters.

Output: Return true if the string is good, or false otherwise.

Example: Output: true

Constraints:

• Output is a boolean value.

Goal: The goal is to check if all characters in the string have the same frequency.

Steps:

• Count the frequency of each character in the string.

• Check if all the frequencies are the same.

Goal: The length of the string will be between 1 and 1000 characters, and all characters are lowercase English letters.

Steps:

• 1 <= s.length <= 1000

• s consists of lowercase English letters.

Assumptions:

• The string s is non-empty and consists of only lowercase letters.

• Input: Example 1: s = "abbcaa"

• Explanation: In this case, both 'a', 'b', and 'c' appear twice in the string. Hence, all characters have the same frequency, and the output is true.

• Input: Example 2: s = "aabbbcc"

• Explanation: In this case, 'a' appears twice, 'b' appears three times, and 'c' appears twice. The frequencies are not all the same, so the output is false.

Approach: To solve the problem, the approach is to count the frequency of each character in the string and check if all characters have the same frequency.

Observations:

• If all characters have the same frequency, the string is good.

• We need to count character occurrences and compare them to determine if they are all the same.

Steps:

• Initialize an array to count the frequency of each character.

• Traverse the string and update the frequency of each character.

• Find the maximum frequency and compare all other frequencies to it.

Empty Inputs:

• An empty string would trivially be a good string, but this case is not valid based on constraints.

Large Inputs:

• Handle strings near the upper constraint limit (1000 characters).

Special Values:

• Strings where all characters are the same will always return true.

Constraints:

• Check for strings with a small number of characters to ensure the logic handles both small and large inputs efficiently.

bool areOccurrencesEqual(string s) {
    int cnt[26] = {}, m_cnt = 0;
    for (auto ch : s)
        m_cnt = max(m_cnt, ++cnt[ch - 'a']);
    return all_of(begin(cnt), end(cnt), [&m_cnt](int t){ return t == 0 || t == m_cnt; });
}

1 : Function Declaration

bool areOccurrencesEqual(string s) {

Declare the function `areOccurrencesEqual` which takes a string `s` as input.

2 : Variable Initialization

    int cnt[26] = {}, m_cnt = 0;

Initialize an array `cnt` of size 26 to store the frequency of each character in the string, and `m_cnt` to track the maximum frequency of any character.

3 : For Loop (Character Iteration)

    for (auto ch : s)

Iterate through each character `ch` in the string `s`.

4 : Max Frequency Update

        m_cnt = max(m_cnt, ++cnt[ch - 'a']);

Update `m_cnt` to the maximum of the current `m_cnt` and the updated count of the character `ch` in `cnt`.

5 : Final Check

    return all_of(begin(cnt), end(cnt), [&m_cnt](int t){ return t == 0 || t == m_cnt; });

Return `true` if all character counts are either 0 or equal to the maximum frequency `m_cnt`; otherwise, return `false`.

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

Average Case: O(n), since we need to iterate through the string once to count frequencies.

Worst Case: O(n), since checking frequencies requires a single pass through the string.

Description: The time complexity is linear in the length of the string due to the need to iterate over the string and count character occurrences.

Best Case: O(26), as we only store the frequency counts of each character.

Worst Case: O(26), since there are at most 26 unique lowercase English letters.

Description: The space complexity is constant because we only need to store the frequency of 26 characters.

Leetcode 1941: Check if All Characters Have Equal Number of Occurrences

Explore →