#1897

Easy

LeetCode Problem Workspace

Redistribute Characters to Make All Strings Equal

Determine if you can redistribute characters among strings so that all strings become identical using a counting approach.

hash table string counting

Problem Statement

Given an array of strings words, you can repeatedly pick any character from one string and insert it into another string at any position. Determine whether it is possible to make all strings in words equal by performing this operation any number of times.

Each string consists of lowercase English letters. Return true if it is possible to make every string equal after redistribution, otherwise return false. Consider the character counts across all strings when evaluating feasibility.

Examples

Example 1

Input: words = ["abc","aabc","bc"]

Output: true

Move the first 'a' in words[1] to the front of words[2], to make words[1] = "abc" and words[2] = "abc". All the strings are now equal to "abc", so return true.

Example 2

Input: words = ["ab","a"]

Output: false

It is impossible to make all the strings equal using the operation.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Solution Approach

Count Total Characters

Create a hash table to count the total occurrences of each character across all strings. This allows quick checking if redistribution is possible based on frequency divisibility.

Check Divisibility by String Count

For each character in the hash table, verify if the total count is divisible by the number of strings. If all characters satisfy this, you can redistribute characters evenly.

Return Result Based on Frequency Check

If any character count is not divisible, return false immediately. Otherwise, return true after checking all characters, confirming that the strings can be made equal.

Complexity Analysis

Metric	Value
Time	O(n \cdot k)
Space	O(1)

Time complexity is O(n * k) where n is the number of strings and k is the average string length, due to counting each character. Space complexity is O(1) because only 26 lowercase letters are counted regardless of input size.

What Interviewers Usually Probe

Notice that the order of characters in strings does not matter, only total counts matter.
Check for divisibility by the number of strings as a quick feasibility check.
Consider edge cases with strings of different lengths or empty strings.

Common Pitfalls or Variants

Common pitfalls

Ignoring the character frequency divisibility check and trying to simulate movements directly.
Assuming character positions matter rather than just counts.
Overlooking edge cases where a character total count is not divisible by the number of strings.

Follow-up variants

Modify the problem to include uppercase letters or digits, changing the hash table size.
Limit the number of allowed moves and determine if equality is still achievable.
Allow only adjacent character swaps and analyze feasibility differently.

FAQ

What is the main idea behind Redistribute Characters to Make All Strings Equal?

The main idea is counting each character's total frequency and checking if it is divisible by the number of strings to allow even redistribution.

Can I ignore character positions when solving this problem?

Yes, only the frequency of characters matters; positions within strings are irrelevant for equality.

What is the time complexity for this solution?

The time complexity is O(n * k) because each character in every string must be counted.

How does GhostInterview handle impossible cases?

It checks character count divisibility first, quickly returning false if any character cannot be evenly distributed.

Does this problem rely on a specific algorithm pattern?

Yes, it follows a Hash Table plus String pattern, where counting frequencies determines feasibility of redistribution.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        cnt = Counter()
        for w in words:
            for c in w:
                cnt[c] += 1
        n = len(words)
        return all(v % n == 0 for v in cnt.values())

Continue Practicing

#1876 substrings of size three with distinct characters #1941 check if all characters have equal number of occurrences #1790 check if one string swap can make strings equal