Redistribute Characters to Make All Strings Equal

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’ 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
Explanation: 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.

Hints:
Characters are independent—only the frequency of characters matters.
It is possible to distribute characters if all characters can be divided equally among all strings.

GoLang: Redistribute Characters to Make All Strings Equal

Make a map with keys are type of rune and values are integer counters. Iterate over all strings and all characters, and then check if the frequencies for each character is divisble by length of the string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func makeEqual(words []string) bool {
    var c = make(map[rune]int)
    for _, s := range words {
        for _, ch := range s {
            c[ch] ++
        }
    }
    for _, v := range c {
        if v % len(words) != 0 {
            return false
        }
    }
    return true
}

func makeEqual(words []string) bool {
    var c = make(map[rune]int)
    for _, s := range words {
        for _, ch := range s {
            c[ch] ++
        }
    }
    for _, v := range c {
        if v % len(words) != 0 {
            return false
        }
    }
    return true
}

Time complexity O(MN) where M is the number of the strings, and N is the average number of characters in each string. Space complexity is also O(MN) but given the characters are lowercase English letters only, we can consider it O(1).

Python: Redistribute Characters to Make All Strings Equal

We can concatenate the words (list of strings) into a string and then use the Counter to count the frequencies for all characters.

1
2
3
4
5
6
7
8
9

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        s = reduce(lambda a, b: a + b, words)
        c = Counter(s)
        for i in c:
            if c[i] % n != 0:
                return False
        return True

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        s = reduce(lambda a, b: a + b, words)
        c = Counter(s)
        for i in c:
            if c[i] % n != 0:
                return False
        return True

We can simply use the all to check if all frequencies are divisble by the length of the words.

1
2
3
4
5

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        s = reduce(lambda a, b: a + b, words) # or s = ''.join(words)
        return all([x % n == 0 for x in Counter(s).values()])

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        n = len(words)
        s = reduce(lambda a, b: a + b, words) # or s = ''.join(words)
        return all([x % n == 0 for x in Counter(s).values()])

C++: Redistribute Characters to Make All Strings Equal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        unordered_map<char, int> data;
        for (auto &n: words) {
            for (auto &c: n) {
                data[c] ++;
            }
        }
        for (auto &[a, b]: data) {
            if (b % words.size() != 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool makeEqual(vector<string>& words) {
        unordered_map<char, int> data;
        for (auto &n: words) {
            for (auto &c: n) {
                data[c] ++;
            }
        }
        for (auto &[a, b]: data) {
            if (b % words.size() != 0) {
                return false;
            }
        }
        return true;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —