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:

1Input: s = "abacbc"
2Output: true
3Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

1Input: s = "aaabb"
2Output: false
3Explanation: The characters that appear in s are 'a' and 'b'.
4'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.

Solution

This problem clearly asks us to find the frequency of each character. If the frequency of each character is same, then we return true. This means this problem definitely needs HashMap to store the frequencies. This is straight forward solution.

 1class Solution {
 2    public boolean areOccurrencesEqual2(String s) {
 3        if (s == null || s.length() == 0) {
 4            return true;
 5        }
 6        Map<Character, Integer> frequency = new HashMap<>();
 7        for (char c: s.toCharArray()) {
 8            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
 9        }
10        int occurrences = frequency.get(s.charAt(0));
11        for (Map.Entry<Character, Integer> entry: frequency.entrySet()) {
12            if (entry.getValue() != occurrences) {
13                return false;
14            }
15        }
16        return true;
17    }
18}
  • Time Complexity: O(n) because we need to iterate through at most n characters of the string s.
  • Space Complexity: O(1) because at most we can have 26 keys in the frequency map.

Now, if we think about it, it can also be solved using arrays because all characters are lowercase English characters, that means we need to store up to 26 characters which is fair for storing them in an array of fixed size. The first iteration would allow us to store the frequency of each character in their respective index position in the array. In next small iteration, we are looking for first character frequency, so as soon as we find a frequency count which is non-zero (the default for integer array), that will be the frequecy of the first chracter. Next, we need to iterate through this count array to make sure all non-zero entries match this frequency we found for the first character. If not, we found at least one entry that did not match the frequency and hence we return false. At the end of the loop, if no such entries found, that means all entries have same frequency and we return true.

 1class Solution {
 2    public boolean areOccurrencesEqual(String s) {
 3        if (s == null || s.length() == 0) {
 4            return true;
 5        }
 6        int[] count = new int[MAX_SIZE];
 7        // create array with default values as 0
 8        for (char c: s.toCharArray()) {
 9            count[c - 'a']++;
10        }
11        int occurrences = 0;
12        for (int i = 0; i < MAX_SIZE; i++) {
13            // get first occurrences number
14            if (count[i] != 0) {
15                occurrences = count[i];
16                break;
17            }
18        }
19        for (int i = 0; i < MAX_SIZE; i++) {
20            if (count[i] != 0 && count[i] != occurrences) {
21                return false;
22            }
23        }
24        return true;
25    }
26}
  • Time Complexity: O(n) because we have to iterate through n characters of string s
  • Space Complexity: O(1) because we have finite number of English lowercase characters (26) in input and hence max array size for count is finite.