algoadvance

Given a string s, determine if all characters in the string have the same number of occurrences.

Clarifying Questions

1. Input Constraints:
   • What is the length range of the string s?
     • The string can have a length ranging from 1 to (10^5).
   • What kind of characters does the string contain?
     • The string contains only lowercase English letters.
2. Output:
   • Return True if all characters in the string have the same number of occurrences; otherwise, return False.

Strategy

1. Data Structure: Use a dictionary to count the frequency of each character in the string.
2. Steps:
   1. Traverse the string s and count the occurrences of each character using a dictionary.
   2. Extract the set of values (frequencies) from the dictionary.
   3. If the length of the set of frequencies is 1, return True (indicating all characters have the same frequency). Otherwise, return False.

Time Complexity

• Time Complexity: (O(n)), where (n) is the length of the string s. This is because we traverse the string once to count the characters and then perform operations on a fixed size set of frequencies.

• Space Complexity: (O(1)) or (O(26)) considering the fixed number of lowercase English letters, which can be considered as constant space (O(1)).

Code

def areOccurrencesEqual(s: str) -> bool:
    # Dictionary to store the frequency of each character
    freq_dict = {}
    
    # Count the frequencies of each character
    for char in s:
        if char in freq_dict:
            freq_dict[char] += 1
        else:
            freq_dict[char] = 1
    
    # Set to store unique frequencies
    freq_set = set(freq_dict.values())
    
    # If there's only one unique frequency, return True
    return len(freq_set) == 1

Example

1. Input: s = "abacbc"
   • Frequencies: {‘a’: 2, ‘b’: 2, ‘c’: 2}
   • Unique Frequencies: {2}
   • Output: True
2. Input: s = "aaabb"
   • Frequencies: {‘a’: 3, ‘b’: 2}
   • Unique Frequencies: {2, 3}
   • Output: False

This approach ensures we efficiently check whether all characters in the string s occur the same number of times.

Try our interview co-pilot at AlgoAdvance.com

• 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?