easy Redistribute Characters to Make All Strings Equal

Problem Statement

Given an array of strings words, return true if you can make all strings equal in words array by performing any number of swap operations. Otherwise, return false.

In one swap operation, you can pick any two indices i and j, and move any characters from words[i] to any position of the words[j].

Examples

Example 1:
- Input: words = ["aaa","bbb","ccc", "abc"]
- Expected Output: true
- Justification: Each string has 3 characters of a single type, and the last string has all 3 characters. We can redistribute the characters to form a string like "abc" making the distribution equal.
Example 2:
- Input: words = ["ab","bc","cd","de","ea"]
- Expected Output: false
- Justification: The characters cannot be redistributed to make all strings equal because all characters appear only twice, making equal distribution impossible.
Example 3:
- Input: words = ["zzx","xzz","zxz"]
- Expected Output: true
- Justification: We can redistribute characters to have each string contain one "x" and two "z"s, like "zzx", "xzz", "zxz", maintaining equal distribution.

Try it yourself

Try solving this question here:

✅ Solution Redistribute Characters to Make All Strings Equal

Problem Statement

Given an array of strings words, return true if you can make all strings equal in words array by performing any number of swap operations. Otherwise, return false.

In one swap operation, you can pick any two indices i and j, and move any characters from words[i] to any position of the words[j].

Examples

Example 1:
- Input: words = ["aaa","bbb","ccc", "abc"]
- Expected Output: true
- Justification: Each string has 3 characters of a single type, and the last string has all 3 characters. We can redistribute the characters to form a string like "abc" making the distribution equal.
Example 2:
- Input: words = ["ab","bc","cd","de","ea"]
- Expected Output: false
- Justification: The characters cannot be redistributed to make all strings equal because all characters appear only twice, making equal distribution impossible.
Example 3:
- Input: words = ["zzx","xzz","zxz"]
- Expected Output: true
- Justification: We can redistribute characters to have each string contain one "x" and two "z"s, like "zzx", "xzz", "zxz", maintaining equal distribution.

Solution

To solve this problem, we'll focus on counting the frequency of each character across all strings and then check if these frequencies can be divided evenly by the number of strings. This approach works because, for the characters to be distributable equally, the total occurrences of each character must be a multiple of the number of strings. This method is effective as it simplifies the problem to a straightforward mathematical check, avoiding the need for complex manipulations or redistributions of the characters.

Our strategy will involve two main steps: first, creating a comprehensive count of each character's appearances across all strings. This is achieved by iterating through each string and incrementing the count for each character. Second, we'll verify if each character's total count is divisible by the number of strings. If all characters pass this test, it implies an equal distribution is possible; otherwise, it is not. This method is chosen for its efficiency and simplicity, directly addressing the problem's core requirement without unnecessary complexity.

Step-by-step algorithm

Initialize a Character Frequency Map: Create an empty map (or dictionary) to keep track of the frequency of each character across all the strings. The key will be the character, and the value will be the count of how many times that character appears.
Count Character Frequencies: Iterate over each string in the input array. For each string, iterate over each character and update the character frequency map by increasing the count for each character.
Check for Equal Distribution:
- Calculate the number of strings in the input array. This will be used to check if a character can be evenly distributed.
- Iterate over the values in the character frequency map. For each frequency value, check if it is divisible by the number of strings. If any frequency is not divisible, return false, indicating that an equal distribution is not possible.
- If all frequencies are divisible by the number of strings, return true.

Algorithm Walkthrough

Input: ["aaa","bbb","ccc", "abc"]

Step 1: Initialize a character frequency map. It will be empty initially: {}.
Step 2: Count character frequencies.
- For the first string "aaa", update the map: {'a': 3}.
- For the second string "bbb", update the map: {'a': 3, 'b': 3}.
- For the third string "ccc", update the map: {'a': 3, 'b': 3, 'c': 3}.
- For the fourth string "abc", update the map: {'a': 4, 'b': 4, 'c': 4}.
Step 3: Check for equal distribution.
- The number of strings is 4.
- Check divisibility for each character frequency:
  - {'a': 4}: 4 % 4 == 0, so 'a' can be evenly distributed.
  - {'b': 4}: 4 % 4 == 0, so 'b' can be evenly distributed.
  - {'c': 4}: 4 % 4 == 0, so 'c' can be evenly distributed.
- Since all characters can be evenly distributed, return true.

Code

java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean makeEqual(String[] words) {
        Map<Character, Integer> charCount = new HashMap<>();
        // Counting frequency of each character in all strings
        for (String word : words) {
            for (char c : word.toCharArray()) {
                charCount.put(c, charCount.getOrDefault(c, 0) + 1);
            }
        }
        
        int numWords = words.length;
        // Checking if each character's frequency is divisible by the number of strings
        for (int count : charCount.values()) {
            if (count % numWords != 0) {
                return false;
            }
        }
        
        return true; // All characters are evenly distributable
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        // Testing with the example inputs
        System.out.println(solution.makeEqual(new String[]{"aaa","bbb","ccc","abc"})); // true
        System.out.println(solution.makeEqual(new String[]{"ab","bc","cd","de","ea"})); // false
        System.out.println(solution.makeEqual(new String[]{"zzx","xzz","zxz"})); // true
    }
}

Complexity Analysis

Time Complexity: The time complexity of the algorithm is , where N is the number of strings in the input array and M is the average length of these strings. This complexity arises because the algorithm iterates through each character of each string to count the frequency of characters.

Space Complexity: The space complexity of the algorithm is , where K is the number of unique characters across all strings. This space is required to store the frequency of each character in a hash map or dictionary. The maximum size of this map depends on the size of the character set used in the strings.

🤖 Don't fully get this? Learn it with Claude

Stuck on Redistribute Characters to Make All Strings Equal? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Redistribute Characters to Make All Strings Equal** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Redistribute Characters to Make All Strings Equal** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Redistribute Characters to Make All Strings Equal**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Redistribute Characters to Make All Strings Equal**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Coin Change Add Binary →