Redistribute Characters to Make All Strings Equal - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given an array of strings. Characters can be moved between strings any number of times. The goal is to determine if all strings can be rearranged so every string becomes identical after redistribution.
Approach 1: Count Character Frequencies (O(n) time, O(1) space)
The key observation: if redistribution is allowed, the only constraint is whether the total count of each character can be evenly divided across all strings. Iterate through every word and count character frequencies using a hash map or fixed-size array. Let k be the number of strings. For each character, check if frequency % k == 0. If any character fails this condition, equal redistribution is impossible. This approach works because every final string must receive the same number of each character. The algorithm scans all characters once and performs constant-time checks, making it efficient for large inputs. This technique relies on simple hash table or array counting, common in many string manipulation problems.
Approach 2: Optimize with Early Return (O(n) time, O(1) space)
This version keeps the same frequency counting idea but introduces an early termination check. While counting characters across the words, track totals and stop immediately once it becomes clear a character cannot be evenly distributed. In practice, this means validating divisibility as soon as counts are finalized instead of performing a full second pass. The complexity remains linear in the total number of characters n, but it slightly reduces unnecessary iterations in large inputs. This approach still relies on simple counting logic and fixed alphabet constraints (26 lowercase letters).
Recommended for interviews: The frequency counting approach is the expected solution. It shows you recognize the redistribution invariant: equal strings require each character count to be divisible by the number of strings. A brute-force simulation of moving characters would be unnecessary and inefficient. Interviewers typically expect the O(n) counting solution because it demonstrates pattern recognition with hash maps and string frequency analysis.
Approach 1: Count Character Frequencies
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.
Complexity
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.
Approach 2: Optimize with Early Return
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.
Complexity
Time Complexity: O(n * m), potentially improved due to early exit. Space Complexity: O(1).
Approach 3: Counting
According to the problem description, as long as the occurrence count of each character can be divided by the length of the string array, it is possible to redistribute the characters to make all strings equal.
Therefore, we use a hash table or an integer array of length 26 cnt to count the occurrences of each character. Finally, we check if the occurrence count of each character can be divided by the length of the string array.
The time complexity is O(L), and the space complexity is O(|\Sigma|). Here, L is the total length of all strings in the array words, and \Sigma is the character set, which is the set of lowercase letters, so |\Sigma|=26.
Complexity Comparison
| 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). |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Character Frequencies | O(n) | O(1) | General case. Best solution for interview and production. |
| Optimize with Early Return | O(n) | O(1) | When working with large datasets and you want to stop as soon as redistribution becomes impossible. |
Video Solution
Redistribute Characters to Make All Strings Equal - Leetcode 1897 - Python • NeetCodeIO • 15,903 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Redistribute Characters to Make All Strings Equal easy or hard?
Redistribute Characters to Make All Strings Equal Python/Java solution
How to solve Redistribute Characters to Make All Strings Equal in O(n)?
What is the best approach for Redistribute Characters to Make All Strings Equal?
Is Redistribute Characters to Make All Strings Equal asked at Google/Amazon/Meta?
What data structure is used in Redistribute Characters to Make All Strings Equal?
What is the time complexity of Redistribute Characters to Make All Strings Equal?
Ready to solve this problem?
Practice Redistribute Characters to Make All Strings Equal with our built-in code editor and test cases.
Practice on FleetCode