Redistribute Characters to Make All Strings Equal solution and explanation
9 more videos on this problem
Redistribute Characters to Make All Strings Equal - Leetcode 1897 - PythonNeetCodeIO · 6:35 · 15K views
Redistribute Characters to Make All Strings Equal | 3 Ways | C++ | JAVA | Leetcode 1897codestorywithMIK · 18:37 · 4K views
Leetcode 1897. Redistribute Characters to Make All Strings Equal [Java]if else statement · 4:50 · 955 views
1897. Redistribute Characters to Make All Strings Equal (Leetcode Easy)Programming Live with Larry · 4:00 · 558 views
Leetcode | 1897. Redistribute Characters to Make All Strings Equal | Easy | Java SolutionDeveloper Docs · 7:40 · 476 views
LeetCode 1897, Redistribute Characters to Make All Strings Equal, Python| Master Programming SkillsThe CodingBuddies Guild · 10:38 · 243 views
Redistribute Characters to Make All Strings Equal - LeetCode #1897 - Python, JavaScript, Java, C++CodingNinja · 5:02 · 197 views
Daily Leetcode #1369: Dec 30, 2023 - 1897. Redistribute Characters to Make All Strings EqualProgramming Live with Larry · 3:29 · 166 views
Solving LeetCode 1897 Redistribute Characters to Make All Strings Equal | Hashing Problem | EasyCode Harmony · 10:23 · 164 views
LeetCode 1897 - Redistribute Characters to Make All Strings Equal - PythonAlpha-Code · 8:26 · 85 views
The 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.
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.
def canMakeEqual(words):
charCount = [0] * 26
n = len(words)
for word in words:
for char in word:
charCount[ord(char) - ord('a')] += 1
return all(count % n == 0 for count in charCount)
print(canMakeEqual(["abc", "aabc", "bc"]))import java.util.*;
public class Main {
public static boolean canMakeEqual(String[] words) {
int[] charCount = new int[26];
int n = words.length;
for (String word : words) {
for (char c : word.toCharArray()) {
charCount[c - 'a']++;
}
}
for (int count : charCount) {
if (count % n != 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] words = {"abc", "aabc", "bc"};
System.out.println(canMakeEqual(words));
}
}#include <iostream>
#include <vector>
bool canMakeEqual(std::vector<std::string>& words) {
int charCount[26] = {0};
int n = words.size();
for (const std::string& word : words) {
for (char c : word) {
charCount[c - 'a']++;
}
}
for (int count : charCount) {
if (count % n != 0) {
return false;
}
}
return true;
}
int main() {
std::vector<std::string> words = {"abc", "aabc", "bc"};
std::cout << (canMakeEqual(words) ? "true" : "false") << std::endl;
return 0;
}function canMakeEqual(words) {
const charCount = new Array(26).fill(0);
const n = words.length;
for (const word of words) {
for (const char of word) {
charCount[char.charCodeAt(0) - 97]++;
}
}
return charCount.every(count => count % n === 0);
}
console.log(canMakeEqual(["abc", "aabc", "bc"]));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool canMakeEqual(char **words, int wordsSize) {
int charCount[26] = {0};
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; words[i][j] != '\0'; j++) {
charCount[words[i][j] - 'a']++;
}
}
for (int k = 0; k < 26; k++) {
if (charCount[k] % wordsSize != 0) {
return false;
}
}
return true;
}
int main() {
char *words[] = {"abc", "aabc", "bc"};
int wordsSize = 3;
printf("%s\n", canMakeEqual(words, wordsSize) ? "true" : "false");
return 0;
}using System;
public class Solution {
public static bool CanMakeEqual(string[] words) {
int[] charCount = new int[26];
int n = words.Length;
foreach (string word in words) {
foreach (char c in word) {
charCount[c - 'a']++;
}
}
foreach (int count in charCount) {
if (count % n != 0) return false;
}
return true;
}
public static void Main() {
string[] words = {"abc", "aabc", "bc"};
Console.WriteLine(CanMakeEqual(words));
}
}This Python function similarly maintains a frequency count in a list. It then checks if each count is divisible by the number of strings. The logic detects possible equalization of all strings by character redistribution.
Time Complexity: O(n * m). Space Complexity: O(1).
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.
def canMakeEqualOptimized(words):
charCount = [0] * 26
n = len(words)
for word in words:
for char in word:
charCount[ord(char) - ord('a')] += 1
for count in charCount:
if count != 0 and count % n != 0:
return False
return True
print(canMakeEqualOptimized(["abc", "aabc", "bc"]))import java.util.*;
public class MainOptimized {
public static boolean canMakeEqualOptimized(String[] words) {
int[] charCount = new int[26];
int n = words.length;
for (String word : words) {
for (char c : word.toCharArray()) {
charCount[c - 'a']++;
}
}
for (int count : charCount) {
if (count != 0 && count % n != 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] words = {"abc", "aabc", "bc"};
System.out.println(canMakeEqualOptimized(words));
}
}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.
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.
function makeEqual(words: string[]): boolean {
const cnt: Record<string, number> = {};
for (const w of words) {
for (const c of w) {
cnt[c] = (cnt[c] || 0) + 1;
}
}
const n = words.length;
return Object.values(cnt).every(v => v % n === 0);
}func makeEqual(words []string) bool {
cnt := [26]int{}
for _, w := range words {
for _, c := range w {
cnt[c-'a']++
}
}
n := len(words)
for _, v := range cnt {
if v%n != 0 {
return false
}
}
return true
}impl Solution {
pub fn make_equal(words: Vec<String>) -> bool {
let mut cnt = std::collections::HashMap::new();
for word in words.iter() {
for c in word.chars() {
*cnt.entry(c).or_insert(0) += 1;
}
}
let n = words.len();
cnt.values().all(|&v| v % n == 0)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Count Character Frequencies | Time Complexity: O(n * m). Space Complexity: O(1). |
| Optimize with Early Return | Time Complexity: O(n * m), potentially improved due to early exit. Space Complexity: O(1). |
| Counting | – |
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. |
Frequently asked questions
Is Redistribute Characters to Make All Strings Equal easy or hard?
Redistribute Characters to Make All Strings Equal is classified as an Easy problem on LeetCode. The challenge mainly tests recognition of a counting invariant and basic string frequency manipulation rather than complex algorithms.
Redistribute Characters to Make All Strings Equal Python/Java solution
Both Python and Java implementations follow the same idea: count characters across all words and verify divisibility by the number of strings. Python often uses collections.Counter or a list of size 26, while Java commonly uses an int[26] array for counting.
How to solve Redistribute Characters to Make All Strings Equal in O(n)?
Traverse all strings and count the occurrences of each character. Let k be the number of strings. For every character, check if its total frequency is divisible by k. If any character fails the divisibility check, return false; otherwise return true. This single pass counting strategy achieves O(n) time complexity.
What is the best approach for Redistribute Characters to Make All Strings Equal?
The best approach is counting character frequencies across all strings. Compute the total frequency of each character and check whether it is divisible by the number of strings. If every character count is divisible, redistribution is possible. This runs in O(n) time with O(1) space using a fixed-size array for 26 lowercase letters.
Is Redistribute Characters to Make All Strings Equal asked at Google/Amazon/Meta?
String frequency and redistribution problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact LeetCode problem may not always appear, the pattern of counting characters and validating constraints is a common interview concept.
What data structure is used in Redistribute Characters to Make All Strings Equal?
The solution uses a frequency counter implemented with either a hash table or a fixed-size integer array of length 26. Since the problem involves lowercase English letters, an array is typically preferred for constant-time access and minimal memory overhead.
What is the time complexity of Redistribute Characters to Make All Strings Equal?
The optimal solution runs in O(n) time where n is the total number of characters across all strings. Each character is processed once while building the frequency count. Space complexity is O(1) because the alphabet size is fixed (26 lowercase letters).