Redistribute Characters to Make All Strings Equal

Redistribute Characters to Make All Strings Equal - Problem

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.

Input & Output

Example 1 — Even Distribution Possible

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

› Output: true

💡 Note: We have 3 'a's, 3 'b's, and 3 'c's total. Since we have 3 strings, each can get exactly 1 of each character. Final result could be ["abc", "abc", "abc"].

Example 2 — Uneven Character Count

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

› Output: false

💡 Note: We have 2 'a's and 1 'b' but 2 strings. Each string should get 1 'a' and 0.5 'b', but we can't split characters.

Example 3 — Single Character Type

$ Input: words = ["a","aa","aaa"]

› Output: true

💡 Note: Total of 6 'a's can be evenly distributed among 3 strings, giving 2 'a's per string: ["aa", "aa", "aa"].

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
words[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings with different characters

Redistribute

Move characters freely between strings

Check

Determine if all strings can become equal

Key Takeaway

🎯 Key Insight: Since characters can be moved freely between strings, we only need to verify that each character's total count is divisible by the number of strings

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that characters can be freely moved between strings, so we only need to check if each character's total count can be evenly distributed. The frequency counting approach solves this optimally in O(n) time by counting each character and checking divisibility by the number of strings.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Counting - Optimal Solution	O(n)	O(1)	Count character frequencies and check if each can be evenly distributed
Brute Force - Try All Redistributions	O(k^n)	O(k)	Recursively try all possible character movements between strings

Frequency Counting - Optimal Solution — Algorithm Steps

Count total characters - must be divisible by number of strings
Count frequency of each character across all strings
Check if each character count is divisible by number of strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Characters

Count frequency of each character across all strings

Check Divisibility

Verify each character count is divisible by number of strings

Return Result

True if all characters can be evenly distributed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char words[][101], int wordsSize) {
    // Check if total characters can be evenly distributed
    int totalChars = 0;
    for (int i = 0; i < wordsSize; i++) {
        totalChars += strlen(words[i]);
    }
    
    if (totalChars % wordsSize != 0) {
        return false;
    }
    
    // Count frequency of each character
    int charCount[128] = {0}; // ASCII characters
    for (int i = 0; i < wordsSize; i++) {
        for (int j = 0; j < strlen(words[i]); j++) {
            charCount[words[i][j]]++;
        }
    }
    
    // Check if each character can be evenly distributed
    for (int i = 0; i < 128; i++) {
        if (charCount[i] > 0 && charCount[i] % wordsSize != 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array of strings
    char words[1000][101];
    int wordsSize = 0;
    
    char* token = strtok(line, "[],\"");
    while (token != NULL && wordsSize < 1000) {
        if (strlen(token) > 0 && strcmp(token, "\n") != 0) {
            strcpy(words[wordsSize], token);
            wordsSize++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    bool result = solution(words, wordsSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all characters in all strings to count frequencies

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 lowercase letters (constant space)

✓ Linear Space

34.3K Views

Medium Frequency

~8 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Counting - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler