1897. Redistribute Characters to Make All Strings Equal
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:
- Creating a counter to tally the frequency of each character across all strings in the
words
. - Iterating over each string in the
words
array, and then over each character in these strings, updating the counter for each character. - Checking if each character's count is divisible by the number of strings
n
. This is achieved with theall
function, which iteratively applies the modulo operation to each count value and returnsTrue
if all results are zero; otherwiseFalse
.
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.
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:
-
We initialize the
Counter
object with no elements.counter = Counter()
-
We then iterate over the list of
words
, and for eachword
inwords
, we iterate over eachcharacter
to update our counter.for word in words: for c in word: counter[c] += 1
Here,
counter[c] += 1
is incrementing the count for the characterc
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. -
After populating the
Counter
, we obtain the total number of stringsn
in the originalwords
array.n = len(words)
-
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
.return all(count % n == 0 for count in counter.values())
This line uses a generator expression inside the
all
function. The expressioncount % n == 0
checks whether the count of each character is a multiple of the number of strings. Theall
function then checks whether this condition isTrue
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
We first initialize an empty
Counter
object that will count the frequency of each character across all the strings.counter = Counter()
-
We then iterate over each
word
in our array (["axx","xay","yaa"]
) and, for eachword
, we iterate over eachcharacter
to update our counter. Thus we get:# After processing "axx" counter = {'a': 1, 'x': 2} # After processing "xay" counter += {'x': 1, 'a': 1, 'y': 1} # After processing "yaa" counter += {'y': 1, 'a': 2} # Final counter counter = {'a': 4, 'x': 3, 'y': 2}
-
We then determine the total number of
words
in the array, which is 3 in our case.n = len(words) # n = 3
-
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.return all(count % n == 0 for count in counter.values())
The
all
function will check:4 % 3 == 0 # False for character 'a' 3 % 3 == 0 # True for character 'x' 2 % 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
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.
A heap is a ...?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!