{x}
blog image

Redistribute Characters to Make All Strings Equal

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

 

Example 1:

Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Move the first 'a' in words[1] to the front of words[2],
to make words[1] = "abc" and words[2] = "abc".
All the strings are now equal to "abc", so return true.

Example 2:

Input: words = ["ab","a"]
Output: false
Explanation: It is impossible to make all the strings equal using the operation.

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.

Solution Explanation: Redistributing Characters to Make All Strings Equal

The problem asks whether it's possible to make all strings in an input array equal by moving characters between them. The key insight is that this is possible if and only if the count of each character across all strings is a multiple of the number of strings. If this condition is met, we can redistribute the characters evenly.

Approach:

  1. Character Counting: We first count the occurrences of each character (a-z) across all strings in the input array words. This is efficiently done using a hash map (or an array of size 26, since we only deal with lowercase English letters).

  2. Divisibility Check: After counting, we check if the count of each character is divisible by the number of strings (words.length). If any character count is not divisible, it means we cannot evenly distribute that character among all strings, making it impossible to make them all equal.

Time Complexity: O(L), where L is the total number of characters across all strings. We iterate through each character once to count it.

Space Complexity: O(1). We use a fixed-size array (or hash map with a limited number of keys) of size 26 to store character counts. This is constant space regardless of the input size.

Code Implementations:

The following code demonstrates the solution in several programming languages:

Python:

from collections import Counter
 
class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        cnt = Counter()
        for word in words:
            cnt.update(word)  #Efficiently updates counts from the word
        n = len(words)
        return all(count % n == 0 for count in cnt.values())

Java:

class Solution {
    public boolean makeEqual(String[] words) {
        int[] counts = new int[26];
        for (String word : words) {
            for (char c : word.toCharArray()) {
                counts[c - 'a']++;
            }
        }
        int n = words.length;
        for (int count : counts) {
            if (count % n != 0) {
                return false;
            }
        }
        return true;
    }
}

C++:

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        vector<int> counts(26, 0);
        for (const string& word : words) {
            for (char c : word) {
                counts[c - 'a']++;
            }
        }
        int n = words.size();
        for (int count : counts) {
            if (count % n != 0) {
                return false;
            }
        }
        return true;
    }
};

JavaScript:

/**
 * @param {string[]} words
 * @return {boolean}
 */
var makeEqual = function(words) {
    const counts = new Array(26).fill(0);
    for (const word of words) {
        for (const char of word) {
            counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
    }
    const n = words.length;
    for (const count of counts) {
        if (count % n !== 0) {
            return false;
        }
    }
    return true;
};

Go:

func makeEqual(words []string) bool {
    counts := make([]int, 26)
    for _, word := range words {
        for _, char := range word {
            counts[char-'a']++
        }
    }
    n := len(words)
    for _, count := range counts {
        if count%n != 0 {
            return false
        }
    }
    return true
}

These code snippets all follow the same fundamental algorithm: counting characters and then checking divisibility. The choice of language mainly affects the syntax and data structure used for character counting (e.g., Counter in Python, arrays in Java/C++/Go, etc.). The core logic remains consistent across all implementations.