Redistribute Characters to Make All Strings Equal

EASY

Description

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

Checkout 2 different approaches to solve Redistribute Characters to Make All Strings Equal. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we use a fixed-size array of 26 integers, which does not depend on the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Redistribute Characters to Make All Strings Equal. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Redistribute Characters to Make All Strings Equal

Patterns:

Counting

Data Structures:

Hash TableString

Companies:

Moengage |