Problem Description

You have an array of strings called words (0-indexed).

You can perform operations to move characters between strings. In each operation:

• Pick two different indices i and j
• words[i] must be a non-empty string
• Move any single character from words[i] to any position in words[j]

The goal is to determine if it's possible to make all strings in the array equal by performing any number of these operations.

Return true if you can make every string in words equal, and false otherwise.

The key insight is that you can redistribute characters freely between strings. For all strings to become equal, each unique character in the entire collection must appear a total number of times that can be evenly divided among all strings.

For example, if you have 3 strings and the character 'a' appears 6 times total across all strings, then each final equal string could have exactly 2 'a's. But if 'a' appears 7 times total, it's impossible to distribute evenly among 3 strings.

The solution counts the total occurrences of each character across all strings using a Counter. Then it checks if each character count is divisible by the number of strings (n). If all character counts are divisible by n, return true; otherwise return false.

Intuition

When we can move characters freely between strings, we need to think about what the final state would look like if all strings become equal.

If all strings end up being identical, and we have n strings total, then each string must contain exactly the same characters in the same quantities. This means that for any character that appears in our collection of strings, its total count must be perfectly divisible by n.

Think of it like distributing items equally among people - if you have 12 apples and 3 people, each person gets exactly 4 apples. But if you have 13 apples and 3 people, there's no way to distribute them equally without splitting an apple.

The same logic applies here. Since we can move characters around freely (but cannot create or destroy them), the total pool of characters remains constant. For example:

• If we have ["abc", "aabc", "bc"] (3 strings)
• Character 'a' appears 3 times total → 3 ÷ 3 = 1 per string ✓
• Character 'b' appears 3 times total → 3 ÷ 3 = 1 per string ✓
• Character 'c' appears 3 times total → 3 ÷ 3 = 1 per string ✓
• All strings can become "abc"

But if we have ["ab", "a"] (2 strings):

• Character 'a' appears 2 times → 2 ÷ 2 = 1 per string ✓
• Character 'b' appears 1 time → 1 ÷ 2 = 0.5 per string ✗
• Impossible to make equal strings

Therefore, the solution is straightforward: count all characters across all strings, then check if each character's count is divisible by the number of strings.

Solution Approach

The implementation uses a counting approach with a hash table to track character frequencies across all strings.

Step 1: Count all characters

We initialize a Counter object (which is a specialized dictionary for counting) to store the frequency of each character across all strings:

cnt = Counter()
for w in words:
    for c in w:
        cnt[c] += 1

This nested loop iterates through each word w in the words array, then through each character c in that word, incrementing the count for that character. After this step, cnt contains the total occurrences of each unique character.

Step 2: Check divisibility

We need to verify that each character's count can be evenly distributed among all strings:

n = len(words)
return all(v % n == 0 for v in cnt.values())

• First, we get the total number of strings n
• Then we use Python's all() function with a generator expression to check if every value v in the counter is divisible by n
• The modulo operator % returns 0 if v is perfectly divisible by n
• all() returns True only if all character counts are divisible by n, otherwise False

Time Complexity: O(m) where m is the total number of characters across all strings (sum of lengths of all words)

Space Complexity: O(k) where k is the number of unique characters (at most 26 for lowercase English letters)

The elegance of this solution lies in its simplicity - instead of simulating the actual character movements, we directly check the mathematical condition that must be satisfied for equal distribution to be possible.

Example Walkthrough

Let's walk through the solution with a concrete example: words = ["abc", "aabc", "bc"]

Step 1: Count all characters across all strings

We'll go through each word and count every character:

• Word "abc": a=1, b=1, c=1
• Word "aabc": a=2, b=1, c=1
• Word "bc": b=1, c=1

Total counts: {'a': 3, 'b': 3, 'c': 3}

Step 2: Check if each count is divisible by the number of strings

We have n = 3 strings total.

Now check each character:

• 'a' appears 3 times: 3 % 3 = 0 ✓ (can give 1 'a' to each string)
• 'b' appears 3 times: 3 % 3 = 0 ✓ (can give 1 'b' to each string)
• 'c' appears 3 times: 3 % 3 = 0 ✓ (can give 1 'c' to each string)

Since all character counts are divisible by 3, we return true. Each string can become "abc".

Counter-example: words = ["ab", "a"]

Count characters:

• Total counts: {'a': 2, 'b': 1}
• We have n = 2 strings

Check divisibility:

• 'a' appears 2 times: 2 % 2 = 0 ✓
• 'b' appears 1 time: 1 % 2 = 1 ✗ (cannot split 1 'b' evenly between 2 strings)

Since 'b' cannot be evenly distributed, we return false.

Solution Implementation

Time and Space Complexity

The time complexity is O(L), where L is the total length of all strings in the array words. This is because the algorithm iterates through each word in the list and then through each character in that word exactly once to count the frequency of each character. The final check all(v % n == 0 for v in cnt.values()) iterates through at most 26 values (the size of the alphabet), which is O(1) relative to the input size.

The space complexity is O(|Σ|), where Σ is the character set (lowercase English letters), so |Σ| = 26. The Counter object cnt stores at most 26 key-value pairs, one for each distinct lowercase letter that appears in the input strings. This space requirement is constant and independent of the input size L.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting Edge Cases with Empty Words Array

A common mistake is not considering what happens when the input array is empty or contains only one string.

Pitfall Example:

def makeEqual(self, words: List[str]) -> bool:
    char_count = Counter()
    for word in words:
        for char in word:
            char_count[char] += 1
  
    num_words = len(words)  # Could be 0!
    return all(count % num_words == 0 for count in char_count.values())

Issue: If words is empty, num_words becomes 0, leading to a division by zero error when checking count % 0.

Solution:

def makeEqual(self, words: List[str]) -> bool:
    # Handle edge cases
    if len(words) <= 1:
        return True  # Empty array or single word is already "equal"
  
    char_count = Counter()
    for word in words:
        for char in word:
            char_count[char] += 1
  
    num_words = len(words)
    return all(count % num_words == 0 for count in char_count.values())

2. Misunderstanding the Problem - Thinking Order Matters

Some might incorrectly assume that the final equal strings need to maintain character order or that characters can only be moved to specific positions.

Pitfall Thinking: "If I have ['abc', 'def'], I can't make them equal because 'a' can't become 'd'"

Correct Understanding: Characters can be freely redistributed. With ['abc', 'def'], we have 1 of each character (a,b,c,d,e,f), and since we can't divide 1 evenly between 2 strings, the answer is false. But if we had ['abc', 'bca'], we have 2 a's, 2 b's, 2 c's, which can be distributed to form ['abc', 'abc'].

3. Using Wrong Data Structure or Manual Counting

Attempting to manually track character counts with a regular dictionary or array can lead to errors.

Pitfall Example:

def makeEqual(self, words: List[str]) -> bool:
    char_count = {}
    for word in words:
        for char in word:
            if char not in char_count:
                char_count[char] = 0  # Forgot to initialize to 0
            char_count[char] += 1
    # ... rest of code

Issue: Manual dictionary management is error-prone and verbose.

Solution: Use Counter from collections, which handles initialization automatically and provides cleaner code.

4. Incorrect Divisibility Check Logic

Using the wrong condition for checking if redistribution is possible.

Pitfall Example:

def makeEqual(self, words: List[str]) -> bool:
    # ... counting logic ...
  
    # Wrong: Checking if any (instead of all) counts are divisible
    return any(count % num_words == 0 for count in char_count.values())

Issue: Using any() instead of all() would return true if even one character can be evenly distributed, which is incorrect. ALL characters must be evenly distributable.

Solution: Always use all() to ensure every character count is divisible by the number of words.