Redistribute Characters to Make All Strings Equal

How it works

This approach uses the same divisibility principle but with a clever optimization. Instead of storing full counts and checking divisibility at the end, we track counts modulo n and use a flag counter to know whether all characters are evenly distributable.

When a character's frequency becomes divisible by n, it means that character can be perfectly distributed. We increment a flag when this happens and decrement it when a new character appears (since it starts at count 1, which is not divisible by n unless n = 1). At the end, if the flag is 0, all characters are evenly distributable.

Steps

1. Create a frequency array of size 26 (for lowercase letters) and initialize a flag counter to 0.
2. For each character encountered:
   • If its current frequency is non-zero, increment it. If the new count is divisible by n, increment the flag.
   • If its current frequency is zero, increment it to 1. If 1 is not divisible by n, decrement the flag.
   • Take the frequency modulo n to keep values small.
3. Return true if the flag equals 0, meaning all characters have counts divisible by n.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(1) since we have at most 26 different characters.

Where n is the number of words and m is the average length of each word.

Things to watch for

Forgetting to Check Divisibility by n

A common mistake is to only check if the total character count is even or to compare character counts between words directly. The key insight is that each character's total count must be divisible by n (the number of words), not just divisible by 2. For example, with 3 words and 4 occurrences of 'a', redistribution is impossible because 4 is not divisible by 3.

Assuming Words Must Already Be Similar

Some solutions incorrectly assume that redistribution is only possible if the words already share some characters or have similar lengths. In reality, the order and current arrangement of characters within each word is irrelevant. The only thing that matters is whether the global character counts allow for even distribution across all n words.

from typing import List

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        freq = [0] * 26
        flag = 0
        n = len(words)

        for w in words:
            for c in w:
                i = ord(c) - ord('a')
                if freq[i] != 0:
                    freq[i] += 1
                    if freq[i] % n == 0:
                        flag += 1
                else:
                    freq[i] += 1
                    if freq[i] % n != 0:
                        flag -= 1
                freq[i] %= n

        return flag == 0

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        vector<int> freq(26, 0);
        int flag = 0;
        int n = words.size();

        for (const string& w : words) {
            for (char c : w) {
                int i = c - 'a';
                if (freq[i] != 0) {
                    freq[i]++;
                    if (freq[i] % n == 0) {
                        flag++;
                    }
                } else {
                    freq[i]++;
                    if (freq[i] % n != 0) {
                        flag--;
                    }
                }
                freq[i] %= n;
            }
        }

        return flag == 0;
    }
};