Check if All Characters Have Equal Number of Occurrences
EasyPrompt
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 <= 1000sconsists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach avoids using an explicit frequency map. It first identifies the unique characters in the string. Then, it calculates the frequency of the first unique character and uses this as the target frequency. Finally, it iterates through the remaining unique characters, calculates their frequencies one by one, and compares them against the target frequency.
Algorithm
- Create a
Setto store the unique characters from the input strings. This takes one pass through the string. - If the set is empty or contains only one character, the condition is trivially met, so return
true. - Take the first character from the set and calculate its frequency by iterating through the entire string
s. Store this frequency astargetCount. - Iterate through the rest of the unique characters in the set.
- For each character, calculate its frequency by iterating through
sagain. - If this new frequency does not match
targetCount, returnfalse. - If the loop completes without finding any mismatch, it means all characters have the same frequency. Return
true.
Walkthrough
This method works by first finding all the unique characters present in the string. It then picks one of these characters, counts how many times it appears in the original string, and sets this count as the 'target' frequency. After that, it does the same for every other unique character, comparing its frequency to the target. If any character's frequency is different, the string is not 'good', and we can immediately return false. If we check all unique characters and find that all their frequencies match the target, the string is 'good', and we return true.
import java.util.HashSet;import java.util.Set; class Solution { public boolean areOccurrencesEqual(String s) { Set<Character> uniqueChars = new HashSet<>(); for (char c : s.toCharArray()) { uniqueChars.add(c); } if (uniqueChars.size() <= 1) { return true; } int targetCount = -1; for (char uniqueChar : uniqueChars) { int currentCount = 0; for (char c : s.toCharArray()) { if (c == uniqueChar) { currentCount++; } } if (targetCount == -1) { targetCount = currentCount; } else if (targetCount != currentCount) { return false; } } return true; }}Complexity
Time
O(U * N), where N is the length of the string and U is the number of unique characters. We iterate through U unique characters, and for each one, we iterate through the entire string of length N. Since U is at most 26, this is technically O(N), but it involves multiple passes over the string, making it less efficient than single-pass solutions.
Space
O(U) to store the set of unique characters. For lowercase English letters, U <= 26, so the space is O(1).
Trade-offs
Pros
Simple to understand logic.
Doesn't require complex data structures besides a Set.
Cons
Inefficient due to repeated scanning of the input string.
The time complexity has a larger constant factor (up to 26 passes) compared to other approaches.
Solutions
Solution
class Solution {public boolean areOccurrencesEqual(String s) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt[s.charAt(i) - 'a']; } int x = 0; for (int v : cnt) { if (v > 0) { if (x == 0) { x = v; } else if (x != v) { return false; } } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.