1897. Redistribute Characters to Make All Strings Equal

EasyHash TableStringCounting
Leetcode Link

Problem Description

The LeetCode problem presents us with a scenario where we're provided an array of strings and we're asked to determine if it's possible to make all strings within the array equal by performing a series of operations. Here, the operation consists of moving any character from one string to any position in another string, keeping in mind that the strings are non-empty and the indices chosen for each operation should be distinct.

The goal is to see if we can use these operations to transform the array so all strings in the array are identical.

For example, if the input array is ["abc","aabc","bc"], we can perform operations to move characters around until all strings become "abc." Thus, in this case, the answer would be true.

If the operation can be successfully performed to make every string equal using any number of operations, we return true. If not, we return false.

Intuition

The intuition behind the solution is based on the frequency of each character across all strings. Since we are allowed to move characters freely between strings, what really matters is whether the total count of each distinct character in the input array is divisible by the number of strings. If that's true for every character, then we can distribute the characters evenly among all strings, making them all equal.

To arrive at the solution approach, consider the following points:

  • We can only move characters between strings, so the total number of each character must remain the same.
  • To make all strings equal, each string must have an identical character count for every individual character.
  • The length of all strings will be equal if we can make them identical, and this length must be a multiple of the number of strings.
  • If the total count of any character isn't a multiple of the number of strings in the array, it's impossible to distribute that character evenly across all strings.

The provided Python solution implements this logic by:

  1. Creating a counter to tally the frequency of each character across all strings in the words.
  2. Iterating over each string in the words array, and then over each character in these strings, updating the counter for each character.
  3. Checking if each character's count is divisible by the number of strings n. This is achieved with the all function, which iteratively applies the modulo operation to each count value and returns True if all results are zero; otherwise False.

If the all function returns True, then it is possible to make all strings in the array equal using the allowed operations. If it returns False, then it is not possible.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The implementation of the solution utilizes a Counter from the Python collections module, which is a specialized dictionary used for counting hashable objects. Here's how the algorithm flows:

  1. We initialize the Counter object with no elements.

    1counter = Counter()
  2. We then iterate over the list of words, and for each word in words, we iterate over each character to update our counter.

    1for word in words:
    2    for c in word:
    3        counter[c] += 1

    Here, counter[c] += 1 is incrementing the count for the character c each time it is encountered. This step essentially builds a frequency map where the key is the character and the value is the total number of times it appears across all strings in the array.

  3. After populating the Counter, we obtain the total number of strings n in the original words array.

    1n = len(words)
  4. The last step is to determine if it is possible to make all strings equal by checking that each character count is divisible by n.

    1return all(count % n == 0 for count in counter.values())

    This line uses a generator expression inside the all function. The expression count % n == 0 checks whether the count of each character is a multiple of the number of strings. The all function then checks whether this condition is True for every element in the counter's values.

If every character can be evenly distributed among the strings, all will return True, meaning that we can make all strings equal by the defined operations. If even one character cannot be evenly distributed, all will return False, which means it's impossible to make all strings equal using any number of the specified operations.

This approach works effectively for this problem because it abstracts away all specifics regarding actual character positions and movements, focusing only on the overall character counts, which is the core aspect of the problem given the unrestricted nature of the allowed operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above. Consider the input array ["axx","xay","yaa"]. The goal is to determine if it's possible to make all these strings equal by moving characters between strings.

Following the suggested steps:

  1. We first initialize an empty Counter object that will count the frequency of each character across all the strings.

    1counter = Counter()
  2. We then iterate over each word in our array (["axx","xay","yaa"]) and, for each word, we iterate over each character to update our counter. Thus we get:

    1# After processing "axx"
    2counter = {'a': 1, 'x': 2}
    3# After processing "xay"
    4counter += {'x': 1, 'a': 1, 'y': 1}
    5# After processing "yaa"
    6counter += {'y': 1, 'a': 2}
    7# Final counter
    8counter = {'a': 4, 'x': 3, 'y': 2}
  3. We then determine the total number of words in the array, which is 3 in our case.

    1n = len(words)  # n = 3
  4. The last step is to check if every character count is divisible by n, the number of strings. We apply the modulus operation to see if there is any remainder.

    1return all(count % n == 0 for count in counter.values())

    The all function will check:

    14 % 3 == 0  # False for character 'a'
    23 % 3 == 0  # True for character 'x'
    32 % 3 == 0  # False for character 'y'

Given that not every character can be evenly distributed across the three strings (since 4 % 3 and 2 % 3 do not yield a zero remainder), the all function will return False. This means it's impossible to make all strings equal using the allowed operations for the input array ["axx","xay","yaa"].

In conclusion, the solution applies a frequency count logic which, when coupled with the modulo operation to check for divisibility by the number of strings, allows us to efficiently determine whether all strings can be made equal according to the problem's rules.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def makeEqual(self, words: List[str]) -> bool:
5        # Initialize a Counter to keep track of the frequency of each character.
6        char_counter = Counter()
7      
8        # Iterate over each word in the list and count the characters.
9        for word in words:
10            for char in word:
11                char_counter[char] += 1
12              
13        # Calculate the number of words to check if characters can be evenly distributed.
14        num_words = len(words)
15      
16        # If each character's count is divisible by the number of words,
17        # then it is possible to rearrange characters to make all words equal.
18        for count in char_counter.values():
19            if count % num_words != 0:
20                return False  # If not divisible by num_words, can't make all words equal.
21      
22        return True  # All characters are evenly distributed across words.
23
1class Solution {
2
3    /**
4     * Checks if characters from 'words' can be redistributed equally.
5     * 
6     * @param words Array of strings to be evaluated.
7     * @return boolean True if characters can be redistributed equally, False otherwise.
8     */
9    public boolean makeEqual(String[] words) {
10        // Array to count the occurrences of each character.
11        int[] charCounts = new int[26];
12      
13        // Loop over each word in the array.
14        for (String word : words) {
15            // Increment the count for each character in the word.
16            for (char c : word.toCharArray()) {
17                charCounts[c - 'a']++;
18            }
19        }
20      
21        // Number of words in the array.
22        int numWords = words.length;
23      
24        // Check that each character's count is divisible by the number of words.
25        for (int count : charCounts) {
26            if (count % numWords != 0) {
27                // If a character's count isn't divisible by numWords,
28                // equal redistribution isn't possible.
29                return false;
30            }
31        }
32      
33        // If all characters could be redistributed equally, return true.
34        return true;
35    }
36}
37
1class Solution {
2public:
3    // Method to check if the characters of the given words can be rearranged 
4    // to make all the words equal
5    bool makeEqual(vector<string>& words) {
6        // Initialize a counter vector to count the occurrences of each letter
7        vector<int> letterCounter(26, 0);
8
9        // Loop over each word in the vector
10        for (const string& word : words) {
11            // Count the occurrences of each character in the word
12            for (char c : word) {
13                ++letterCounter[c - 'a']; // Increment the count for the character
14            }
15        }
16
17        int numWords = words.size(); // Store the total number of words
18      
19        // Loop over the counter and check if each character's total count
20        // is divisible by the number of words, otherwise return false
21        for (int count : letterCounter) {
22            if (count % numWords != 0) {
23                return false; // If not divisible, we can't make all words equal
24            }
25        }
26      
27        // If all counts are divisible, return true
28        return true;
29    }
30};
31
1function makeEqual(words: string[]): boolean {
2    // Get the number of words to determine if letters can be distributed equally
3    let wordCount = words.length;
4    // Initialize an array for the 26 letters of the English alphabet, all starting at 0
5    let letterCounts = new Array(26).fill(0);
6
7    // Iterate through each word in the array
8    for (let word of words) {
9        // Iterate through each letter in the word
10        for (let char of word) {
11            // Increment the count of this letter in the `letterCounts` array
12            letterCounts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
13        }
14    }
15
16    // Check if each letter's count can be evenly divided by the number of words
17    for (let count of letterCounts) {
18        if (count % wordCount !== 0) {
19            // If a letter cannot be evenly divided, return false
20            return false;
21        }
22    }
23    // If all letters can be evenly divided, return true
24    return true;
25}
26
Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N * M), where N is the number of words in the input list words and M is the average length of the words. This is because the code consists of a nested loop where the outer loop iterates over each word in words, and the inner loop iterates over each character in the word. Each character is then added to the counter, which is an operation that takes O(1) time on average. Because every character in every word is processed once, the total time taken is proportional to the total number of characters in all words combined.

Space Complexity

The space complexity of the code is O(U), where U is the number of unique characters across all words. This is due to the use of the counter which stores a count for each distinct character. Since the number of unique characters is limited by the character set being used (in this case, usually the lowercase English letters, which would be at most 26), the space used by the counter could be considered fixed for practical purposes. However, in the most general case where any characters could appear, the space complexity is bounded by the number of unique characters U.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫