Watch 10 video solutions for Redistribute Characters to Make All Strings Equal, a easy level problem involving Hash Table, String, Counting. This walkthrough by NeetCodeIO has 15,779 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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. |