Check if All Characters Have Equal Number of Occurrences solution and explanation
9 more videos on this problem
LeetCode 1941 Solution ( Check if All Characters Have Equal Number of Occurrences )Engineering Digest · 3:49 · 2K views
LeetCode 1941. Check if All Characters Have Equal Number of Occurrences | 🏆 Biweekly Contest 57Cherry Coding [IIT-G] · 5:25 · 1K views
Leetcode | 1941. Check if All Characters Have Equal Number of Occurrences | Easy | Java SolutionDeveloper Docs · 5:21 · 1K views
Leetcode Solution - 1941 Check if All Characters Have Equal Number of OccurrencesJohn Leonardo · 3:51 · 784 views
1941. Check if All Characters Have Equal Number of Occurrences (Leetcode Easy)Programming Live with Larry · 3:03 · 558 views
Check if All Characters Have Equal Number of Occurrences - LeetCode 1941 - Java Solutionalgobest - Computer Science · 2:40 · 327 views
Check if All Characters Have Equal Number of Occurrences - LeetCode 1941 Solution - C++nexTRIE · 4:41 · 318 views
Check if All Characters Have Equal Number of Occurrences LeetCode - JavaCode with Katie · 4:57 · 277 views
LeetCode 1941 - Check if All Characters Have Equal Number of Occurrences: A Microsoft JourneyThe Lofi Dev · 3:40 · 200 views
LeetCode 1941 Check if All Characters Have Equal Number of OccurrencesRajesh Ghosh · 4:35 · 190 views
The problem
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.
Approach overview
Problem Overview: You get a string s. Every character should appear the same number of times. If all characters share an identical frequency, return true; otherwise return false. The task reduces to counting character frequencies and verifying they are equal.
Approach 1: Use a Frequency Dictionary (O(n) time, O(k) space)
The most direct solution counts how many times each character appears using a dictionary or hash map. Iterate through the string once and update the count for each character. After building the frequency map, take the first frequency as a reference and iterate through the remaining counts to ensure they match. Hash lookups and updates run in constant time, so the entire operation is linear in the length of the string. This approach relies on a hash table for fast counting and works efficiently for any string size.
Approach 2: Sort Frequencies (O(n + k log k) time, O(k) space)
Start the same way by counting character occurrences. Store all frequency values in a list and sort the list. If every element in the sorted list is equal to the first element, all characters occur the same number of times. Sorting adds a k log k cost where k is the number of distinct characters, while counting still takes O(n). This approach is slightly less efficient but very easy to reason about because identical frequencies appear consecutively after sorting. The solution still depends on character counting using concepts from counting and string processing.
Recommended for interviews: The frequency dictionary approach is what interviewers expect. It demonstrates that you can model the problem as a counting task and use constant-time hash lookups to achieve O(n) time. The sorting variant is acceptable but slightly less optimal. Showing both indicates you understand tradeoffs between direct frequency comparison and post-processing techniques like sorting.
Approach 1: Use a Frequency Dictionary
This approach leverages a dictionary (or hashmap) to count the occurrences of each character in the string. Once the counts are recorded, we check if all the frequencies are the same.
def areOccurrencesEqual(s: str) -> bool:
from collections import Counter
freq = Counter(s)
return len(set(freq.values())) == 1import java.util.HashMap;
import java.util.HashSet;
public class Solution {
public boolean areOccurrencesEqual(String s) {
HashMap<Character, Integer> freq = new HashMap<>();
for (char ch : s.toCharArray()) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
return new HashSet<>(freq.values()).size() == 1;
}
}#include <unordered_map>
#include <unordered_set>
#include <string>
bool areOccurrencesEqual(std::string s) {
std::unordered_map<char, int> freq;
for (char c : s) {
++freq[c];
}
std::unordered_set<int> countSet;
for (const auto& pair : freq) {
countSet.insert(pair.second);
}
return countSet.size() == 1;
}function areOccurrencesEqual(s) {
const freq = {};
for (const char of s) {
if (!freq[char]) freq[char] = 0;
freq[char]++;
}
const uniqueCounts = new Set(Object.values(freq));
return uniqueCounts.size === 1;
}#include <stdbool.h>
#include <string.h>
bool areOccurrencesEqual(char * s) {
int freq[26] = {0};
for (int i = 0; s[i] != '\0'; i++) {
freq[s[i] - 'a']++;
}
int first_count = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
if (first_count == 0) {
first_count = freq[i];
} else if (freq[i] != first_count) {
return false;
}
}
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool AreOccurrencesEqual(string s) {
var freq = new Dictionary<char, int>();
foreach (var ch in s) {
if (!freq.ContainsKey(ch)) freq[ch] = 0;
freq[ch]++;
}
var uniqueCounts = new HashSet<int>(freq.Values);
return uniqueCounts.Count == 1;
}
}In this Python solution, we use the collections.Counter class to count the occurrences of each character in the string. After obtaining the frequencies, we convert them into a set, which will remove any duplicates. If all the frequencies are the same, the set will contain only one item, so we check if the length of the set is 1.
Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.
Space Complexity: O(1), in terms of the extra space used for the counter and set, assuming a fixed number of possible unique characters (26 for lowercase English letters).
Approach 2: Sort Frequencies
This approach involves counting character frequencies, sorting them, and checking if all sorted values are the same. Although not the most optimal, it's an alternative method to ensure all characters have equal frequency.
def areOccurrencesEqual(s: str) -> bool:
from collections import Counter
freq = Counter(s).values()
freq_list = sorted(freq)
return freq_list[0] == freq_list[-1]import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public boolean areOccurrencesEqual(String s) {
HashMap<Character, Integer> freq = new HashMap<>();
for (char ch : s.toCharArray()) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
ArrayList<Integer> countList = new ArrayList<>(freq.values());
Collections.sort(countList);
return countList.get(0).equals(countList.get(countList.size() - 1));
}
}#include <unordered_map>
#include <vector>
#include <algorithm>
bool areOccurrencesEqual(std::string s) {
std::unordered_map<char, int> freq;
for (char c : s) {
++freq[c];
}
std::vector<int> freqValues;
for (auto& pair : freq) {
freqValues.push_back(pair.second);
}
std::sort(freqValues.begin(), freqValues.end());
return freqValues.front() == freqValues.back();
}function areOccurrencesEqual(s) {
const freq = {};
for (const char of s) {
freq[char] = (freq[char] || 0) + 1;
}
const freqValues = Object.values(freq).sort((a, b) => a - b);
return freqValues[0] === freqValues[freqValues.length - 1];
}#include <stdbool.h>
#include <string.h>
bool areOccurrencesEqual(char* s) {
int freq[26] = {0};
for (int i = 0; s[i] != '\0'; i++) {
freq[s[i] - 'a']++;
}
int min_count = 0, max_count = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
if (min_count == 0) min_count = freq[i];
if (freq[i] != min_count) return false;
}
}
return true;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public bool AreOccurrencesEqual(string s) {
var freq = new Dictionary<char, int>();
foreach (var ch in s) {
if (!freq.ContainsKey(ch)) freq[ch] = 0;
freq[ch]++;
}
var freqValues = freq.Values.ToList();
freqValues.Sort();
return freqValues.First() == freqValues.Last();
}
}Here, we count character occurrences, sort the frequency list, and check the first and last elements since they would differ if any counts were unique.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) beyond input storage, with fixed character counts.
Approach 3: Counting
We use a hash table or an array of length 26 called cnt to record the number of occurrences of each character in the string s.
Next, we traverse each value in cnt and check if all non-zero values are equal.
The time complexity is O(n), and the space complexity is O(|\Sigma|). Here, 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.
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);
}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
}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;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Use a Frequency Dictionary | Time Complexity: O(n), where n is the length of the string, as we iterate through the string once. |
| Sort Frequencies | Time Complexity: O(n log n) due to sorting. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Dictionary | O(n) | O(k) | General case. Fastest and most common interview solution using hash map counting. |
| Sort Frequencies | O(n + k log k) | O(k) | Useful when you want a simple comparison step after sorting frequency values. |
Frequently asked questions
Is Check if All Characters Have Equal Number of Occurrences easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate around 79%. It mainly checks understanding of string traversal and frequency counting using a hash map.
Check if All Characters Have Equal Number of Occurrences Python/Java solution
In Python, a dictionary or collections.Counter is typically used to count characters and compare frequencies. In Java, a HashMap<Character, Integer> performs the same role. Both implementations iterate through the string once and then validate that all counts match.
How to solve Check if All Characters Have Equal Number of Occurrences in O(n)?
Iterate through the string and store character counts in a hash map. After counting, store the first frequency and compare it against every other value in the map. If any count differs, return false; otherwise return true. Both counting and validation together run in O(n) time.
What is the best approach for Check if All Characters Have Equal Number of Occurrences?
The best approach uses a hash table (frequency dictionary). Count occurrences of each character in one pass, then verify that all frequency values are identical. This runs in O(n) time with O(k) space where k is the number of distinct characters.
Is Check if All Characters Have Equal Number of Occurrences asked at Google/Amazon/Meta?
This type of frequency-counting string problem appears frequently in interviews at large tech companies including Amazon, Google, and Meta. It tests basic hash table usage, string traversal, and reasoning about character frequency constraints.
What data structure is used in Check if All Characters Have Equal Number of Occurrences?
The core data structure is a hash table (dictionary or map). It stores each character as a key and its frequency as the value, allowing constant-time updates and lookups during iteration.
What is the time complexity of Check if All Characters Have Equal Number of Occurrences?
The optimal solution runs in O(n) time because each character in the string is processed once while building the frequency map. Checking the frequency values takes O(k) time, where k is the number of unique characters. Overall complexity remains linear.
