algoadvance

Leetcode 1941. Check if All Characters Have Equal Number of Occurrences

Problem Statement

You are given a string s consisting of lowercase English letters. Your task is to determine if all characters in the string have the same number of occurrences.

Return true if all characters have the same frequency, and false otherwise.

Clarifying Questions

  1. Can the input string be empty?
    • No, the problem implies the string will have at least one character.
  2. Are there any constraints on the length of the string?
    • The string can be of length up to (10^4) as per typical Leetcode constraints.
  3. Are there any special characters or only lowercase English letters?
    • The string consists of only lowercase English letters.
  4. Should the solution handle case sensitivity?
    • No, the problem specifies lowercase English letters only.

Strategy

  1. Count the Frequency:
    • Use a hashmap (or a fixed-size array for 26 lowercase letters) to track the frequency of each character in the string.
  2. Check Frequency Equality:
    • After counting, we need to check if all values in the frequency map/array are the same.
  3. Return the Result:
    • If all frequencies are equal, return true; otherwise, return false.

Code

Here’s the implementation in C++:

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

bool areOccurrencesEqual(std::string s) {
    // Step 1: Count the frequency of each character
    std::unordered_map<char, int> frequency;
    for (char c : s) {
        frequency[c]++;
    }
    
    // Step 2: Check if all characters have the same frequency
    std::unordered_set<int> uniqueFrequencies;
    for (const auto& pair : frequency) {
        uniqueFrequencies.insert(pair.second);
    }
    
    // If there is exactly one unique frequency, return true
    return uniqueFrequencies.size() == 1;
}

int main() {
    std::string s = "abacbc";
    if (areOccurrencesEqual(s)) {
        std::cout << "True" << std::endl;
    } else {
        std::cout << "False" << std::endl;
    }
    return 0;
}

Time Complexity

The solution involves two main steps:

  1. Counting Frequencies:
    • This step involves iterating through the string once, giving it a time complexity of (O(n)).
  2. Checking Frequencies:
    • This step involves iterating through the map which in the worst case has 26 entries (one for each lowercase letter), giving it a time complexity of (O(1)).

Overall, the time complexity of the solution is (O(n)), where (n) is the length of the string s. The space complexity is (O(1)) for the fixed set of lowercase letters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI