# Redistribute Characters to Make All Strings Equal
**Difficulty:** EASY
[External](https://leetcode.com/problems/redistribute-characters-to-make-all-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/redistribute-characters-to-make-all-strings-equal
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Moengage](https://scaleengineer.com/companies/moengage)
---
## Problem
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.

# Approaches
## HashMap for Frequency Counting
This approach determines if redistribution is possible by counting the total frequency of each character across all strings. A `HashMap` is used for this purpose. The core principle is that for an even redistribution, the total count of every character must be perfectly divisible by the number of strings.
**Time:** O(L), where L is the total number of characters across all strings in the input array. We iterate through all characters once to build the map, and then iterate through the unique characters (at most 26) to check for divisibility. · **Space:** O(K), where K is the number of unique characters. Since the problem specifies lowercase English letters, K is at most 26, making the space complexity O(1) or constant space.
**Pros:** It's a straightforward and easy-to-understand implementation of the core logic.; It's flexible and would work for any character set without modification.
**Cons:** Using a `HashMap` introduces a slight overhead in terms of time (due to hashing and potential collisions) and memory (for storing map entries) compared to a simple array.
### Explanation
The problem states we can move any character from one string to any position in another. This implies that all characters from all strings can be pooled together and then redistributed. For all strings to become equal, they must all become identical to some target string, say `s`.

This is only possible if the total count of each character in the initial pool is a multiple of the number of strings, `n`. If the total count of a character, say 'x', is `c_x`, then each of the `n` final strings must contain `c_x / n` instances of 'x'. This requires `c_x` to be divisible by `n`. This condition must hold for every character present in the strings.

This approach implements this logic using a `HashMap` to store the frequency of each character.

The algorithm proceeds as follows:
1.  First, we get the number of strings, `n`. If `n` is 1, any redistribution is trivially successful, so we return `true`.
2.  We initialize a `HashMap<Character, Integer>` to map each character to its total count.
3.  We iterate through every string in the `words` array. For each character in the string, we increment its count in the `HashMap`.
4.  After counting all characters, we iterate through the values (counts) stored in the `HashMap`.
5.  For each count, we check if it is divisible by `n`. If we find any count that is not divisible by `n`, it's impossible to make the strings equal, and we return `false`.
6.  If all character counts are divisible by `n`, it means a valid redistribution is possible, and we return `true`.

Here is the Java implementation:
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean makeEqual(String[] words) {
        int n = words.length;
        if (n == 1) {
            return true;
        }

        Map<Character, Integer> counts = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                counts.put(c, counts.getOrDefault(c, 0) + 1);
            }
        }

        for (int count : counts.values()) {
            if (count % n != 0) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Let `n` be the length of the `words` array.
- If `n` is 1, return `true` as a single string is already "equal".
- Create a `HashMap<Character, Integer>` to store character frequencies.
- Iterate through each `word` in the `words` array.
    - For each character `c` in the `word`, increment its count in the map.
- Iterate through the counts in the map's values.
    - If any `count` is not divisible by `n` (i.e., `count % n != 0`), return `false`.
- If the loop completes, return `true`.

## Optimized Frequency Counting with an Array
This is a more efficient version of the frequency counting approach. Knowing that the strings only contain lowercase English letters, we can use a simple integer array of size 26 as a frequency map. This avoids the overhead associated with a `HashMap` and provides better performance.
**Time:** O(L), where L is the total number of characters in all strings. We perform a single pass over all characters to populate the array, and a constant time pass (26 iterations) to check the counts. · **Space:** O(1), as we use a fixed-size array of 26 integers, which does not depend on the input size.
**Pros:** Extremely efficient in both time and space due to direct array access.; Minimal memory usage.; Considered the standard and best practice for frequency counting problems with a fixed, small character set.
**Cons:** The implementation is specific to the character set of lowercase English letters. It would require changes to handle a different or larger character set.
### Explanation
The underlying principle is the same as the HashMap approach: for all strings to be made equal, the total count of each character must be divisible by the number of strings. This optimized approach leverages the constraint that all characters are lowercase English letters to use a more efficient data structure for counting.

Instead of a `HashMap`, we use an integer array `counts` of size 26. Each index in the array corresponds to a letter of the alphabet, e.g., `counts[0]` for 'a', `counts[1]` for 'b', and so on. This direct mapping is faster than hashing.

The algorithm is as follows:
1.  Get the number of strings, `n`. If `n` is 1, return `true`.
2.  Initialize an integer array `counts` of size 26 with all elements as zero.
3.  Iterate through each `word` in the `words` array.
4.  For each character `c` in the `word`, we find its corresponding index by `c - 'a'` and increment the value at that index: `counts[c - 'a']++`.
5.  After populating the `counts` array, we iterate through it from index 0 to 25.
6.  For each `count` in the array, we check if it's divisible by `n`. If `count % n != 0`, we immediately know an equal distribution is impossible and return `false`.
7.  If we check all 26 counts and find they are all divisible by `n`, we return `true`.

Here is the Java implementation:
```java
class Solution {
    public boolean makeEqual(String[] words) {
        int n = words.length;
        if (n == 1) {
            return true;
        }

        int[] counts = new int[26];
        for (String word : words) {
            for (char c : word.toCharArray()) {
                counts[c - 'a']++;
            }
        }

        for (int count : counts) {
            if (count % n != 0) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Let `n` be the length of the `words` array.
- If `n` is 1, return `true`.
- Create an integer array `counts` of size 26, initialized to all zeros.
- Iterate through each `word` in `words`.
    - For each character `c` in `word`, increment `counts[c - 'a']`.
- Iterate through each `count` in the `counts` array.
    - If `count % n != 0`, return `false`.
- If the loop completes, return `true`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def makeEqual(self, words: List[str]) -> bool: counter = Counter() for word in words: for c in word: counter[c] += 1 n = len(words) return all(count % n == 0 for count in counter . values())

```