Redistribute Characters to Make All Strings Equal

Easy

#1731Time: 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.1 company

Patterns

Counting

Data structures

Hash Table String

Companies

Moengage

Prompt

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:

words[1] to the front of words[2],
to make

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Get the number of strings, n. If n is 1, return true.
Initialize an integer array counts of size 26 with all elements as zero.
Iterate through each word in the words array.
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']++.
After populating the counts array, we iterate through it from index 0 to 25.
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.
If we check all 26 counts and find they are all divisible by n, we return true.

Here is the Java implementation:

1class Solution {2    public boolean makeEqual(String[] words) {3        int n = words.length;4        if (n == 1) {5            return true;6        }7 8        int[] counts = new int[26];9        for (String word : words) {10            for (char c : word.toCharArray()) {11                counts[c - 'a']++;12            }13        }14 15        for (int count : counts) {16            if (count % n != 0) {17                return false;18            }19        }20 21        return true;22    }23}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

First, we get the number of strings, n. If n is 1, any redistribution is trivially successful, so we return true.
We initialize a HashMap<Character, Integer> to map each character to its total count.
We iterate through every string in the words array. For each character in the string, we increment its count in the HashMap.
After counting all characters, we iterate through the values (counts) stored in the HashMap.
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.
If all character counts are divisible by n, it means a valid redistribution is possible, and we return true.

Here is the Java implementation:

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean makeEqual(String[] words) {6        int n = words.length;7        if (n == 1) {8            return true;9        }10 11        Map<Character, Integer> counts = new HashMap<>();12        for (String word : words) {13            for (char c : word.toCharArray()) {14                counts.put(c, counts.getOrDefault(c, 0) + 1);15            }16        }17 18        for (int count : counts.values()) {19            if (count % n != 0) {20                return false;21            }22        }23 24        return true;25    }26}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean makeEqual(String[] words) {4    int[] counter = new int[26];5    for (String word : words) {6      for (char c : word.toCharArray()) {7        ++counter[c - 'a'];8      }9    }10    int n = words.length;11    for (int i = 0; i < 26; ++i) {12      if (counter[i] % n != 0) {13        return false;14      }15    }16    return true;17  }18}

1class Solution {2public:3  bool makeEqual(vector<string> &words) {4    vector<int> counter(26, 0);5    for (string word : words) {6      for (char c : word) {7        ++counter[c - 'a'];8      }9    }10    int n = words.size();11    for (int count : counter) {12      if (count % n != 0)13        return false;14    }15    return true;16  }17};

1class Solution:2    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())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem