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.
A more efficient approach is to count the frequencies of all characters in a single pass and store them in a hash map. After counting, we can iterate through the frequencies stored in the map to check if they are all equal.
Algorithm
- Initialize a
HashMap<Character, Integer>to store character frequencies. - Iterate through the input string
sonce. For each character, increment its count in the hash map. - After populating the map, retrieve the frequency of the first character (or any character) in the map. This will be our reference frequency.
- Iterate through all the frequency values in the hash map.
- Compare each frequency with the reference frequency. If any frequency is different, return
false. - If the loop completes, it means all characters that appeared in the string have the same frequency. Return
true.
Walkthrough
This approach uses a HashMap to efficiently store the frequency of each character. We iterate through the string just once to build this map. For example, for the string "abacbc", the map would become {a=2, b=2, c=2}. Once the map is built, we need to check if all the frequency values are the same. We can do this by getting the frequency of the first entry, storing it as a reference, and then iterating through the rest of the frequencies in the map to ensure they all match the reference value. If a mismatch is found, we return false. If the entire map is checked without a mismatch, we return true.
import java.util.HashMap;import java.util.Map; class Solution { public boolean areOccurrencesEqual(String s) { Map<Character, Integer> counts = new HashMap<>(); for (char c : s.toCharArray()) { counts.put(c, counts.getOrDefault(c, 0) + 1); } int frequency = -1; for (int count : counts.values()) { if (frequency == -1) { frequency = count; } else if (frequency != count) { return false; } } return true; }}Complexity
Time
O(N), where N is the length of the string. The first loop to build the map takes O(N) time. The second loop to check the frequencies takes O(U) time, where U is the number of unique characters (U <= 26). Thus, the total time complexity is O(N + U), which simplifies to O(N).
Space
O(U) to store the hash map. Since the string consists of lowercase English letters, U is at most 26. Therefore, the space complexity is O(1).
Trade-offs
Pros
Efficient single-pass counting.
General solution that works for any character set.
Cons
Slightly more overhead than an array-based approach due to hashing and object creation for map entries.
Given that the input string consists only of lowercase English letters, we can optimize the frequency counting process by using a fixed-size array of 26 integers instead of a hash map. This eliminates the overhead of hashing and is generally faster.
Algorithm
- Initialize an integer array
freqof size 26 with all elements as 0. Each indexiin the array will correspond to the character'a' + i. - Iterate through the input string
s. For each characterc, increment the corresponding counter in the array:freq[c - 'a']++. - After counting, find the frequency of the first character that appears in the string. Initialize a variable
targetFreq = 0. - Iterate through the
freqarray. - Skip any zero counts, as they correspond to characters not present in the string.
- If
targetFreqis 0 (meaning this is the first non-zero count we've found), settargetFreqto the current count. - If the current count is non-zero and not equal to
targetFreq, returnfalse. - If the loop finishes, all present characters have the same frequency. Return
true.
Walkthrough
This is the most optimized approach for this problem's constraints. Since we know the characters are limited to the 26 lowercase English letters, we can use a simple integer array of size 26 as a direct-access frequency map. The index 0 of the array stores the count of 'a', index 1 for 'b', and so on. We can calculate the index for any character c with the expression c - 'a'. We first pass through the string to populate this array. Then, we make a second pass through the frequency array itself. We find the first non-zero frequency and store it as our target. Then we continue iterating, and if we find any other non-zero frequency that doesn't match our target, we return false. If we finish checking the array, it means all characters have equal occurrences.
class Solution { public boolean areOccurrencesEqual(String s) { int[] counts = new int[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } int targetFreq = 0; for (int count : counts) { if (count == 0) { continue; // Skip characters that didn't appear } if (targetFreq == 0) { // This is the first character frequency we've found targetFreq = count; } else if (count != targetFreq) { // Found a different frequency return false; } } return true; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once to populate the array (O(N)) and then iterate through the fixed-size array of 26 elements (O(1)). The total time is dominated by the first pass, making it O(N).
Space
O(1). We use an array of a fixed size (26), which does not depend on the input string length.
Trade-offs
Pros
Most efficient approach in terms of both time and space for the given constraints.
Avoids hashing overhead and object allocations, leading to better performance.
Cons
This solution is specific to the character set (lowercase English letters). It would need modification for a different or larger character set.
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; }}class Solution {public: bool areOccurrencesEqual(string s) { int cnt[26]{}; for (char &c : s) { ++cnt[c - 'a']; } int x = 0; for (int &v : cnt) { if (v) { if (!x) { x = v; } else if (x != v) { return false; } } } return true; }};class Solution: def areOccurrencesEqual(self, s: str) -> bool: cnt = Counter(s) return len(set(cnt . values())) == 1Video 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.