Redistribute Characters to Make All Strings Equal — Solution
Redistribute Characters to Make All Strings Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Redistribute Characters to Make All Strings Equal is an easy coding problem on arrays, strings and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of strings words. In one operation you may take any character from any word and move it into any word (possibly the same one).
Return true if some sequence of such operations can make all the strings equal.
Example 1
Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Moving one a and one b from the middle word makes all three "abc".
Example 2
Input: words = ["ab","a"]
Output: false
Explanation: There is one b for two words.
Example 3
Input: words = ["aa","aa","aa"]
Output: true
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters.
Hints for Redistribute Characters to Make All Strings Equal
Hint 1
Characters can move anywhere, so only the totals matter — position and grouping are irrelevant.
Hint 2
If all
nwords end up equal, each letter's total count must split evenly across them.Hint 3
So every letter's total must be divisible by
words.length.
How to solve Redistribute Characters to Make All Strings Equal
Because a character may be moved to any word at no cost, the only invariant is the multiset of all characters. The words can be equalised exactly when that multiset splits into n identical parts.
Approach
- Count every letter across all words into a 26-slot table.
- If any count is not divisible by
words.length, returnfalse. - Otherwise return
true.
Why it works
Necessity: if all n words are the string t, letter c appears n · count_t(c) times overall, a multiple of n. Sufficiency: when every total is divisible by n, hand each word total(c)/n copies of each letter — a valid distribution reachable by moves.
Complexity
- Time —
O(total characters) - Space —
O(1)
Pitfalls
- Comparing word lengths first is unnecessary and can mislead — lengths are allowed to differ before the moves.
- Dividing by the number of characters rather than the number of words is the classic slip.
Reference solution
Python
from typing import List
def makeEqual(words: List[str]) -> bool:
count = [0] * 26
for w in words:
for c in w:
count[ord(c) - 97] += 1
n = len(words)
return all(c % n == 0 for c in count)Java
public static boolean makeEqual(String[] words) {
int[] count = new int[26];
for (String w : words) {
for (int i = 0; i < w.length(); i++) count[w.charAt(i) - 'a']++;
}
for (int c : count) {
if (c % words.length != 0) return false;
}
return true;
}C++
bool makeEqual(vector<string>& words) {
vector<int> count(26, 0);
for (auto& w : words) {
for (char c : w) count[c - 'a']++;
}
int n = (int) words.size();
for (int c : count) {
if (c % n != 0) return false;
}
return true;
}JavaScript
var makeEqual = function(words) {
const count = new Array(26).fill(0);
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words[i].length; j++) count[words[i].charCodeAt(j) - 97]++;
}
for (let i = 0; i < 26; i++) {
if (count[i] % words.length !== 0) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.