Teaching Kids Programming – Redistribute Characters to Make All Strings Equal

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Redistribute Characters to Make All Strings Equal

We can rearrange the letter to any string and any position – thus we just have to check the number of frequencies to see if it is divisble by the number of strings in the list. We use the “”.join to concatenate all the strings into one. And use Counter() to count the number of frequencies for each unique element in the string. Then we iterate over the values which is the frequencies values to check if they are divisible by the number of strings in the list.

1
2
3
4
5
6
7
8
9

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        s = "".join(words)
        c = Counter(s)
        n = len(words)
        for i in c.values():
            if i % n != 0:
                return False
        return True

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        s = "".join(words)
        c = Counter(s)
        n = len(words)
        for i in c.values():
            if i % n != 0:
                return False
        return True

We can merge all into a One-Liner:

1
2
3

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        return all([x % len(words) == 0 for x in Counter(''.join(words)).values()])

class Solution:
    def makeEqual(self, words: List[str]) -> bool:
        return all([x % len(words) == 0 for x in Counter(''.join(words)).values()])

The time complexity is O(N) and space complexity is O(N) where N is the number of the characters in all strings combined.

–EOF (The Ultimate Computing & Technology Blog) —