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' inwords[1] to the front of words[2], to makewords[1]= "abc" and words[2] = "abc". All the strings are now equal to "abc", so returntrue.
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 <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters.This approach involves counting the total number of each character across all strings. For each character, we need to check if its total count is divisible by the number of strings. If this is true for all characters, it implies that we can redistribute them to make all strings equal.
In this C implementation, we use the charCount array to store the frequency of each character in all strings. We iterate over each string and character, updating the frequency. Finally, we check if each character's total count is divisible by the number of strings. This logic determines if redistribution is possible to make all strings equal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of strings and m is the average length of the string. Space Complexity: O(1), since we use only a fixed-size array of 26 integers.
This approach optimizes the solution by adding an early return if a character's count is found to be non-divisible by the number of strings early in the process. This avoids unnecessary subsequent checks, thereby potentially improving performance.
This Python variant implements an early return within the loop examining divisibility. If a non-divisible character count is found, the function stops immediately, improving performance.
Java
Time Complexity: O(n * m), potentially improved due to early exit. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Count Character Frequencies | Time Complexity: O(n * m), where n is the number of strings and m is the average length of the string. Space Complexity: O(1), since we use only a fixed-size array of 26 integers. |
| Optimize with Early Return | Time Complexity: O(n * m), potentially improved due to early exit. Space Complexity: O(1). |
Redistribute Characters to Make All Strings Equal - Leetcode 1897 - Python • NeetCodeIO • 15,346 views views
Watch 9 more video solutions →Practice Redistribute Characters to Make All Strings Equal with our built-in code editor and test cases.
Practice on FleetCode