Redistribute Characters to Make All Strings Equal

Difficulty: Easy | Acceptance: 66.90% | Paid: No Topics: Hash Table, String, Counting

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, pick a character from words[i] and move it to words[j].

Return true if you can make all the strings equal, and false otherwise.

• Examples
• Constraints
• Hash Map Counting
• Array Counting

Examples

Example 1

Input:

words = ["abc","aabc","bc"]

Output:

true

Explanation: Move the first ‘a’ in words[1] to the front of words[2], to make words[1] = “abc” and words[2] = “abc”. All the strings are now equal to “abc”, so return true.

Example 2

Input:

words = ["ab","a"]

Output:

false

Explanation: It is impossible to make all the strings equal using the operation.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Hash Map Counting

Intuition For all strings to be equal after redistribution, the total count of each character across all strings must be evenly divisible by the number of strings.

Steps

• Count the frequency of each character across all strings using a hash map
• Check if every character count is divisible by the number of strings
• If any count is not divisible, return false; otherwise return true

from collections import Counter
from typing import List

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        if n == 1:
            return True
        
        counter = Counter()
        for word in words:
            counter.update(word)
        
        for count in counter.values():
            if count % n != 0:
                return False
        
        return True

Complexity

• Time: O(n × m) where n is the number of strings and m is the average string length
• Space: O(1) since we only store 26 lowercase letters
• Notes: Hash map overhead is minimal for lowercase letters

Array Counting

Intuition Since the input only contains lowercase English letters, we can use a fixed-size array of 26 elements for counting, which is more efficient than a hash map.

Steps

• Create an array of size 26 initialized to zero
• Iterate through all strings and increment the count for each character
• Check if every count is divisible by the number of strings
• Return true if all counts are divisible, false otherwise

from typing import List

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        if n == 1:
            return True
        
        count = [0] * 26
        for word in words:
            for c in word:
                count[ord(c) - ord('a')] += 1
        
        for c in count:
            if c % n != 0:
                return False
        
        return True

Complexity

• Time: O(n × m) where n is the number of strings and m is the average string length
• Space: O(1) fixed array of 26 integers
• Notes: More efficient than hash map for lowercase letters due to direct indexing