Skip to content

1941. Check if All Characters Have Equal Number of Occurrences

SourceBiweekly Contest 57 Q1DifficultyEasyRating1242

Description

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.

Solutions

Solution 1: Counting

Thinking

We only need all letter frequencies equal. After counting, the set of frequencies should be a singleton.

One pass over lowercase letters suffices.

We use a hash table or an array of length \(26\) called \(\textit{cnt}\) to record the number of occurrences of each character in the string \(s\).

Next, we traverse each value in \(\textit{cnt}\) and check if all non-zero values are equal.

The time complexity is \(O(n)\), and the space complexity is \(O(|\Sigma|)\), where \(n\) is the length of the string \(s\), and \(\Sigma\) is the size of the character set. In this problem, the character set consists of lowercase English letters, so \(|\Sigma|=26\).

1
2
3
class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        return len(set(Counter(s).values())) == 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        int v = 0;
        for (int x : cnt) {
            if (x == 0) {
                continue;
            }
            if (v > 0 && v != x) {
                return false;
            }
            v = x;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector<int> cnt(26);
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        int v = 0;
        for (int x : cnt) {
            if (x == 0) {
                continue;
            }
            if (v && v != x) {
                return false;
            }
            v = x;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func areOccurrencesEqual(s string) bool {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    v := 0
    for _, x := range cnt {
        if x == 0 {
            continue
        }
        if v > 0 && v != x {
            return false
        }
        v = x
    }
    return true
}
1
2
3
4
5
6
7
8
function areOccurrencesEqual(s: string): boolean {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    const v = cnt.find(v => v);
    return cnt.every(x => !x || v === x);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    /**
     * @param String $s
     * @return Boolean
     */
    function areOccurrencesEqual($s) {
        $cnt = array_fill(0, 26, 0);
        for ($i = 0; $i < strlen($s); $i++) {
            $cnt[ord($s[$i]) - ord('a')]++;
        }
        $v = 0;
        foreach ($cnt as $x) {
            if ($x == 0) {
                continue;
            }
            if ($v && $v != $x) {
                return false;
            }
            $v = $x;
        }
        return true;
    }
}

Comments