Problem Description

Given an array of strings words, determine if it is possible to redistribute the characters of all the strings such that every string becomes exactly the same. You can freely move any character from one string to another, as long as after redistribution, every string is identical in content and length.

• Each string in words can have different lengths and characters initially.
• You may not add or remove any characters; you can only move them between the strings.
• After redistribution, every string must be identical.
• Return True if it’s possible, False otherwise.

Example:
Input: words = ["abc","aabc","bc"]
Output: True

Thought Process

The core challenge is to check if we can rearrange the characters so that every string ends up being exactly the same.
Naive Approach: One could try to generate all possible redistributions, but this quickly becomes infeasible for larger inputs.
Optimization Insight: Instead, notice that every string must have the same set and count of characters after redistribution. That means, for every character in the combined pool, its total count must be divisible by the number of strings. If not, we can’t evenly split the characters across all strings.

Solution Approach

• Step 1: Count the total number of occurrences of each character across all strings. We use a hash map (dictionary) for this, as it allows O(1) lookups and updates.
• Step 2: For each character in the combined pool, check if its count is divisible by n (the number of strings). If any character fails this check, it’s impossible to redistribute them evenly.
• Step 3: If all characters pass the divisibility test, return True; otherwise, return False.

This approach is efficient because we only need to scan each character once and perform a simple divisibility check.

Example Walkthrough

Sample Input: words = ["abc","aabc","bc"]

1. Count all characters:
   • "abc" → a:1, b:1, c:1
   • "aabc" → a:2, b:1, c:1
   • "bc" → b:1, c:1

   Total counts: a:3, b:3, c:3

2. Check divisibility: There are 3 strings. For each character:
   • a: 3 % 3 = 0
   • b: 3 % 3 = 0
   • c: 3 % 3 = 0

   All counts divide evenly by 3.

3. Conclusion: It is possible to redistribute the characters so that all strings are "abc".

Code Implementation

from collections import Counter

class Solution:
    def makeEqual(self, words):
        total = Counter()
        for word in words:
            total += Counter(word)
        n = len(words)
        for count in total.values():
            if count % n != 0:
                return False
        return True
      

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        unordered_map<char, int> freq;
        for (auto& word : words) {
            for (char c : word) {
                freq[c]++;
            }
        }
        int n = words.size();
        for (auto& p : freq) {
            if (p.second % n != 0)
                return false;
        }
        return true;
    }
};
      

import java.util.*;

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

var makeEqual = function(words) {
    let freq = {};
    for (let word of words) {
        for (let c of word) {
            freq[c] = (freq[c] || 0) + 1;
        }
    }
    let n = words.length;
    for (let key in freq) {
        if (freq[key] % n !== 0)
            return false;
    }
    return true;
};
      

Time and Space Complexity

• Brute-force Approach:
  • Would involve generating all possible redistributions, which is exponential and infeasible for even moderate input sizes.
• Optimized Approach:
  • Time Complexity: O(T), where T is the total number of characters in all words. We scan each character once to count, and then iterate over at most 26 (for lowercase English) unique characters.
  • Space Complexity: O(1) if limited to lowercase English letters (since the frequency array/map is fixed size), or O(U) for U unique characters in general.

Summary

The key insight is that, for all strings to be made equal via redistribution, every character's total count must be divisible by the number of strings. By counting all characters and checking divisibility, we efficiently determine the answer in linear time. This approach is both simple and elegant, avoiding unnecessary computation and making use of basic properties of numbers and strings.