Problem Statement

Given an array of strings words, return true if you can make all strings equal in words array by performing any number of swap operations. Otherwise, return false.

In one swap operation, you can pick any two indices i and j, and move any characters from words[i] to any position of the words[j].

Examples

• Example 1:

  • Input: words = ["aaa","bbb","ccc", "abc"]
  • Expected Output: true
  • Justification: Each string has 3 characters of a single type, and the last string has all 3 characters. We can redistribute the characters to form a string like "abc" making the distribution equal.

• Example 2:

  • Input: words = ["ab","bc","cd","de","ea"]
  • Expected Output: false
  • Justification: The characters cannot be redistributed to make all strings equal because all characters appear only twice, making equal distribution impossible.

• Example 3:

  • Input: words = ["zzx","xzz","zxz"]
  • Expected Output: true
  • Justification: We can redistribute characters to have each string contain one "x" and two "z"s, like "zzx", "xzz", "zxz", maintaining equal distribution.

Solution

To solve this problem, we'll focus on counting the frequency of each character across all strings and then check if these frequencies can be divided evenly by the number of strings. This approach works because, for the characters to be distributable equally, the total occurrences of each character must be a multiple of the number of strings. This method is effective as it simplifies the problem to a straightforward mathematical check, avoiding the need for complex manipulations or redistributions of the characters.

Our strategy will involve two main steps: first, creating a comprehensive count of each character's appearances across all strings. This is achieved by iterating through each string and incrementing the count for each character. Second, we'll verify if each character's total count is divisible by the number of strings. If all characters pass this test, it implies an equal distribution is possible; otherwise, it is not. This method is chosen for its efficiency and simplicity, directly addressing the problem's core requirement without unnecessary complexity.

Step-by-step algorithm

1. Initialize a Character Frequency Map: Create an empty map (or dictionary) to keep track of the frequency of each character across all the strings. The key will be the character, and the value will be the count of how many times that character appears.

2. Count Character Frequencies: Iterate over each string in the input array. For each string, iterate over each character and update the character frequency map by increasing the count for each character.

3. Check for Equal Distribution:

   • Calculate the number of strings in the input array. This will be used to check if a character can be evenly distributed.
   • Iterate over the values in the character frequency map. For each frequency value, check if it is divisible by the number of strings. If any frequency is not divisible, return false, indicating that an equal distribution is not possible.
   • If all frequencies are divisible by the number of strings, return true.

Algorithm Walkthrough

Input: ["aaa","bbb","ccc", "abc"]

• Step 1: Initialize a character frequency map. It will be empty initially: {}.

• Step 2: Count character frequencies.

  • For the first string "aaa", update the map: {'a': 3}.
  • For the second string "bbb", update the map: {'a': 3, 'b': 3}.
  • For the third string "ccc", update the map: {'a': 3, 'b': 3, 'c': 3}.
  • For the fourth string "abc", update the map: {'a': 4, 'b': 4, 'c': 4}.

• Step 3: Check for equal distribution.

  • The number of strings is 4.
  • Check divisibility for each character frequency:
    • {'a': 4}: 4 % 4 == 0, so 'a' can be evenly distributed.
    • {'b': 4}: 4 % 4 == 0, so 'b' can be evenly distributed.
    • {'c': 4}: 4 % 4 == 0, so 'c' can be evenly distributed.
  • Since all characters can be evenly distributed, return true.

Complexity Analysis

Time Complexity: The time complexity of the algorithm is O(N * M), where N is the number of strings in the input array and M is the average length of these strings. This complexity arises because the algorithm iterates through each character of each string to count the frequency of characters.

Space Complexity: The space complexity of the algorithm is O(K), where K is the number of unique characters across all strings. This space is required to store the frequency of each character in a hash map or dictionary. The maximum size of this map depends on the size of the character set used in the strings.