Redistribute Characters to Make All Strings Equal
Problem
You are given an array of strings words. In one operation you may move any character from any string to any position in any string. Return true if you can make every string equal after some number of operations, otherwise false.
words = ["abc", "aabc", "bc"]truedef make_equal(words):
n = len(words)
count = [0] * 26
for w in words:
for ch in w:
count[ord(ch) - ord("a")] += 1
return all(c % n == 0 for c in count)function makeEqual(words) {
const n = words.length;
const count = new Array(26).fill(0);
for (const w of words) {
for (const ch of w) {
count[ch.charCodeAt(0) - 97]++;
}
}
return count.every(c => c % n === 0);
}class Solution {
public boolean makeEqual(String[] words) {
int n = words.length;
int[] count = new int[26];
for (String w : words)
for (char ch : w.toCharArray())
count[ch - 'a']++;
for (int c : count)
if (c % n != 0) return false;
return true;
}
}bool makeEqual(vector<string>& words) {
int n = words.size();
vector<int> count(26, 0);
for (auto& w : words)
for (char ch : w)
count[ch - 'a']++;
for (int c : count)
if (c % n != 0) return false;
return true;
}Explanation
Because a character can be moved freely between any strings, the positions don't matter at all — only the total supply of each letter does. The question reduces to: can the letters be split into n identical piles?
If all n final strings are equal, each must contain the same multiset of characters. So for every letter, its grand total across all words must split evenly into n equal shares.
We tally each of the 26 letters into a frequency array by scanning every character of every word once. This is the entire input cost.
Then the answer is simply whether every count is divisible by n, the number of words. If even one letter's total leaves a remainder, some word would be short that letter and equality is impossible.
Example: ["abc", "aabc", "bc"] with n = 3. Totals are a:3, b:3, c:3 — all divisible by 3 — so each word can become "abc" and the answer is true.