Sponsored
Sponsored
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.
Time Complexity: O(n * m), where n is the number of strings and m is the average length of the string. Space Complexity: O(1), since we use only a fixed-size array of 26 integers.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5bool canMakeEqual(char **words, int wordsSize) {
6 int charCount[26] = {0};
7
8 for (int i = 0; i < wordsSize; i++) {
9 for (int j = 0; words[i][j] != '\0'; j++) {
10 charCount[words[i][j] - 'a']++;
11 }
12 }
13
14 for (int k = 0; k < 26; k++) {
15 if (charCount[k] % wordsSize != 0) {
16 return false;
17 }
18 }
19 return true;
20}
21
22int main() {
23 char *words[] = {"abc", "aabc", "bc"};
24 int wordsSize = 3;
25 printf("%s\n", canMakeEqual(words, wordsSize) ? "true" : "false");
26 return 0;
27}In this C implementation, we use the charCount array to store the frequency of each character in all strings. We iterate over each string and character, updating the frequency. Finally, we check if each character's total count is divisible by the number of strings. This logic determines if redistribution is possible to make all strings equal.
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.
Time Complexity: O(n * m), potentially improved due to early exit. Space Complexity: O(1).
1import java.util.*;
2
3
The Java implementation here also leverages an early exit strategy, providing a performance gain when dealing with strings where early determination of impossibility can be made.