We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Redistribute Characters to Make All Strings Equal

Number: 2025

Difficulty: Easy

Paid? No

Companies: Amazon, Moengage

Problem Description

Given an array of strings, determine whether it is possible to redistribute the characters among the strings (by moving one character at a time from one string to another) such that all strings become equal.

Key Insights

  • The operation allows moving any character between strings, so only the overall frequency of each character matters.
  • For all strings to be identical, each character's total count must be divisible by the number of strings.
  • Count the total frequency for each character and check the divisibility condition.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of strings and m is the average length of the strings. Space Complexity: O(1) (or O(26)) since we use a fixed-size frequency counter for lowercase English letters.

Solution

The approach is to aggregate the frequency of every character from all strings. Since every string must end up with the same multiset of characters, the frequency of each character must be evenly distributable among all strings. This means for each character, the total count must be divisible by the number of strings. We use a hash map or fixed-size array (size 26 for lowercase letters) to count characters. Finally, we check the divisibility condition for every character in the counter.

Code Solutions

# Python solution with line-by-line comments
def makeEqual(words):
    # Number of strings in the list
    num_strings = len(words)
    
    # Initialize a frequency counter for each lowercase letter
    char_count = {}
    
    # Count frequency of each character from all strings
    for word in words:
        for char in word:
            # Increment the count for the character
            char_count[char] = char_count.get(char, 0) + 1
            
    # Check if every character count is divisible by num_strings
    for count in char_count.values():
        if count % num_strings != 0:
            return False
    
    return True

# Example usage:
print(makeEqual(["abc","aabc","bc"]))  # Expected output: True
← Back to All Questions