Redistribute Characters to Make All Strings Equal

Easy
525.

Redistribute Characters to Make All Strings Equal

Redistribute Characters to Make All Strings Equal is an easy coding problem on arrays, strings and counting, asked in Amazon and Adobe interviews.

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {boolean}
 */
var makeEqual = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.

Hints for Redistribute Characters to Make All Strings Equal

  1. Hint 1

    Characters can move anywhere, so only the totals matter — position and grouping are irrelevant.

  2. Hint 2

    If all n words end up equal, each letter's total count must split evenly across them.

  3. 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

  1. Count every letter across all words into a 26-slot table.
  2. If any count is not divisible by words.length, return false.
  3. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings