Check if All Characters Have Equal Number of Occurrences

Check if All Characters Have Equal Number of Occurrences - 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).

Input & Output

Example 1 — Good String

$ Input: s = "abacbc"

› Output: true

💡 Note: Each character appears exactly 2 times: 'a' appears 2 times, 'b' appears 2 times, 'c' appears 2 times. All frequencies are equal.

Example 2 — Bad String

$ Input: s = "aaabb"

› Output: false

💡 Note: Character 'a' appears 3 times but 'b' appears 2 times. The frequencies are not equal.

Example 3 — Single Character

$ Input: s = "c"

› Output: true

💡 Note: Only one unique character 'c' appears 1 time. All characters have the same frequency (trivially true).

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with various characters

Count Frequencies

Count how often each character appears

Check Equality

Verify all frequencies are the same

Key Takeaway

🎯 Key Insight: Count character frequencies using a hash map and verify all counts are equal

Asked in

a Amazon 15 M Microsoft 12

The key insight is to count character frequencies and verify they are all equal. The hash map approach is optimal: count all frequencies in O(n) time, then check equality. Time: O(n), Space: O(k) where k is unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Count	O(n)	O(k)	Use hash map to count all character frequencies in one pass
Brute Force Character Counting	O(n²)	O(1)	Count each character separately and compare all frequencies

Hash Map Frequency Count — Algorithm Steps

Count character frequencies using hash map
Get all frequency values
Check if all frequencies are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Frequency Map

Count each character: {a:2, b:2, c:2}

Extract Frequencies

Get frequency values: [2, 2, 2]

Check Equality

All frequencies equal → return true

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s) {
    int len = strlen(s);
    if (len == 0) return true;
    
    // Count frequency of each character (assuming ASCII)
    int freqMap[256] = {0};
    for (int i = 0; i < len; i++) {
        freqMap[(unsigned char)s[i]]++;
    }
    
    // Find first non-zero frequency
    int firstFreq = 0;
    for (int i = 0; i < 256; i++) {
        if (freqMap[i] > 0) {
            firstFreq = freqMap[i];
            break;
        }
    }
    
    // Check if all frequencies are equal
    for (int i = 0; i < 256; i++) {
        if (freqMap[i] > 0 && freqMap[i] != firstFreq) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies plus O(k) to check equality where k is number of unique characters

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k unique characters where k ≤ n

✓ Linear Space

28.4K Views

Medium Frequency

~10 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler