Problem 1897

(Last updated: )

Question statement

You are given an array of strings words (0-indexed). In one operation, pick two distinct indices $\texttt{i}$ and $\texttt{j}$, where $\texttt{words[i]}$ is a non-empty string, and move any character from $\texttt{words[i]}$ to any position in $\texttt{words[j]}$. Return $\texttt{true}$ if you can make every string in words equal using any number of operations, and $\texttt{false}$ otherwise.

Solution

Main idea:

This is simply a redistribution problem in disguise. A valid rearrangement is possible only if every distinct letter (across all words) appears with a frequency divisible by the length of words. Otherwise, there will exist a letter (counted with multiplicity) that will appear in some but not all words.

  • Join all words into one big string $\texttt{s}$ and hash all distinct elements using a $\texttt{set()}$
  • For $\texttt{i}$ in this set, count the number of occurrences of this $\texttt{i}$ in $\texttt{s}$.
  • If there is a count that is not divisible by $\texttt{len(words)}$, then return $\texttt{False}$
  • Otherwise return $\texttt{True}$.

Code

1
2
3
4
5
6
7
def makeEqual(self, words: List[str]) -> bool:
    str1 = ''.join(words)
    res = set(str1)
    for i in res:
        if str1.count(i)%len(words) !=0:
            return False
    return True

Alternate idea:

You can trade off the built in count function iterating through the non-hashable string, with constructing a dictionary that counts the number of occurrences of each letter across words, and then going across the dictionary to see if each count is divisible by $\texttt{len(words)}$.

Alternate code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def makeEqual2(self, words: List[str]) -> bool:
    dic = {}
    n = len(words)
    for word in words:
        for letter in word:
            if letter in dic:
                dic[letter] +=1
            else:
                dic[letter] = 1

    for letter in dic:
        if(dic[letter] % n != 0):
            return False
    return True

Comments:

In both cases, the time complexity is O($\texttt{len(s)}$).

At the time of submission, the first approach passes leetcode submission cases in 69ms, beating 45.25% of users. It uses 17.38MB of memory, beating 7.46% of users. The second approach passes leetcode submission cases in 75ms, beating 30.2% of users. It uses 17.55MB of memory, beating 6.55% of users.

Looking through other solutions, a few take-aways:

  • Python has a built in $\texttt{Counter()}$ (optimized) function that basically builds the desired dictionary for us. The relevant code seems to be
1
dic: dict[str, int] = Counter(''.join(words))
  • Another pretty cool idea that people seem to use is to join the words together into a string, create an array of length 26, and increment the value at the $\texttt{i}^{th}$ spot whenever the corresponding letter is encountered while scanning through this string. Finally check if each entry in this array is divisible by $\texttt{len(words)}.$