algoadvance

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

Problem Statement

Given a string s, determine if all characters have the same frequency of occurrence in the string.

Clarifying Questions

1. Input Constraints:
   • Is the input string s always non-empty?
   • What is the maximum possible length of the string s?
2. Character Types:
   • Are the characters limited to lowercase and uppercase English letters, or can they include other characters?

Assuming the input string s can contain only lowercase English letters and has a maximum length of 105.

Example

• Example 1:
  • Input: “abacbc”
  • Output: true ('a', 'b', 'c' all appear 2 times)
• Example 2:
  • Input: “aaabb”
  • Output: false ('a' appears 3 times while 'b' appears 2 times)

Strategy

1. Count Frequency:
   • Use a HashMap to count the frequency of each character in the string.
2. Check Equality:
   • Traverse through the HashMap values and ensure all have the same value.

Code

import java.util.HashMap;

public class Solution {
    public boolean areOccurrencesEqual(String s) {
        // Step 1: Count frequency of each character
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        // Step 2: Check if all frequencies are the same
        int frequency = -1;  // Initialize to a value that no frequency will have.
        
        for (int count : frequencyMap.values()) {
            if (frequency == -1) {
                frequency = count;  // Set the frequency upon encountering the first entry
            } else if (frequency != count) {
                return false;  // If any frequency doesn't match, return false
            }
        }
        
        return true;  // All frequencies matched
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed once to count frequencies and then verified.
• Space Complexity: O(1), since the HashMap will at most store counts for 26 different characters (assuming the input consists exclusively of lowercase English letters).

Conclusion

The provided solution efficiently counts character frequencies and checks for equality. The time complexity ensures scalability for large input sizes within the given constraints.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?