Problem

Given a string s, return true ifs _is agood 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).

Examples

Example 1

1
2
3

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

1
2
3
4

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.

Follow Up

A string is also valid if we can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string s, determine if it is valid. If so, return true, otherwise return false.

Example 1

1
2
3

Input: aabbccc
Output: true
Explanation: Remove one 'c' to make all frequencies 2.

Example 2

1
2
3

Input: aaabbbcccd
Output: true
Explanation: Remove 'd' to make all frequencies 3.

Solution

Method 1 – Check with Frequency Array

Intuition

The key idea is that if all characters in the string appear the same number of times, then the set of their frequencies will have only one unique value. For example, in “abacbc”, ‘a’, ‘b’, and ‘c’ all appear 2 times, so the set of frequencies is {2}.

For the follow-up, check if removing one character can make all frequencies equal.

Approach

  1. Create a hash map (or array) to count the frequency of each character in the string.
  2. Collect all the frequency values.
  3. Check if all frequencies are the same by converting them to a set and checking its length.
  4. Return true if all frequencies are equal, otherwise false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        int freq[26] = {0};
        for (char c : s) freq[c - 'a']++;
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (freq[i] == 0) continue;
            if (ans == 0) ans = freq[i];
            else if (freq[i] != ans) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func areOccurrencesEqual(s string) bool {
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }
    ans := 0
    for _, v := range freq {
        if ans == 0 {
            ans = v
        } else if v != ans {
            return false
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        int ans = 0;
        for (int f : freq) {
            if (f == 0) continue;
            if (ans == 0) ans = f;
            else if (f != ans) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun areOccurrencesEqual(s: String): Boolean {
        val freq = IntArray(26)
        for (c in s) freq[c - 'a']++
        var ans = 0
        for (f in freq) {
            if (f == 0) continue
            if (ans == 0) ans = f
            else if (f != ans) return false
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def areOccurrencesEqual(s: str) -> bool:
    freq: dict[str, int] = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    ans = 0
    for v in freq.values():
        if ans == 0:
            ans = v
        elif v != ans:
            return False
    return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn are_occurrences_equal(s: String) -> bool {
        let mut freq = [0; 26];
        for b in s.bytes() {
            freq[(b - b'a') as usize] += 1;
        }
        let mut ans = 0;
        for &f in freq.iter() {
            if f == 0 { continue; }
            if ans == 0 { ans = f; }
            else if f != ans { return false; }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(k) for hash map (k = unique chars) = O(26) = O(1)

Method 2 – Hash Map Frequency Check

Intuition

Count the frequency of each character using a hash map. If all frequencies are the same, the string is valid. This method is more general and works for any character set.

Approach

  1. Count the frequency of each character using a hash map.
  2. Check if all frequencies are the same.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        int val = -1;
        for (auto& [k, v] : freq) {
            if (val == -1) val = v;
            else if (val != v) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public boolean areOccurrencesEqual(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        int val = -1;
        for (int v : freq.values()) {
            if (val == -1) val = v;
            else if (val != v) return false;
        }
        return true;
    }
}
1
2
3
4
5

def areOccurrencesEqual(s: str) -> bool:
    from collections import Counter
    freq = Counter(s)
    vals = list(freq.values())
    return all(v == vals[0] for v in vals)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(k) for hash map (k = unique chars) = O(26) = O(1)

Follow up - Can remove One Character

Method 1 - Hash Map Frequency Check

For the follow-up, check if removing one character can make all frequencies equal.

Approach

  1. Count the frequency of each character using a hash map.
  2. Count the frequency of frequencies.
  3. If there are at most two different frequencies, check if one can be removed to make all equal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool isValidFollowUp(const string& s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        unordered_map<int, int> count;
        for (auto& [k, v] : freq) count[v]++;
        if (count.size() == 1) return true;
        if (count.size() > 2) return false;
        auto it = count.begin();
        int f1 = it->first, c1 = it->second; ++it;
        int f2 = it->first, c2 = it->second;
        if ((f1 == 1 && c1 == 1) || (f2 == 1 && c2 == 1)) return true;
        if ((abs(f1 - f2) == 1) && (c1 == 1 || c2 == 1)) return true;
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public boolean isValidFollowUp(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
        Map<Integer, Integer> count = new HashMap<>();
        for (int v : freq.values()) count.put(v, count.getOrDefault(v, 0) + 1);
        if (count.size() == 1) return true;
        if (count.size() > 2) return false;
        Iterator<Map.Entry<Integer, Integer>> it = count.entrySet().iterator();
        int f1 = it.next().getKey(), c1 = it.next().getValue();
        int f2 = it.hasNext() ? it.next().getKey() : 0, c2 = it.hasNext() ? it.next().getValue() : 0;
        if ((f1 == 1 && c1 == 1) || (f2 == 1 && c2 == 1)) return true;
        if ((Math.abs(f1 - f2) == 1) && (c1 == 1 || c2 == 1)) return true;
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def isValidFollowUp(s: str) -> bool:
    from collections import Counter
    freq = Counter(s)
    count = Counter(freq.values())
    if len(count) == 1:
        return True
    if len(count) > 2:
        return False
    keys = list(count.keys())
    vals = list(count.values())
    if (keys[0] == 1 and vals[0] == 1) or (keys[1] == 1 and vals[1] == 1):
        return True
    if abs(keys[0] - keys[1]) == 1 and (vals[0] == 1 or vals[1] == 1):
        return True
    return False

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(k) for hash map (k = unique chars) = O(26) = O(1)