algoadvance

Given an array of strings words, return true if you can make all strings in words equal using the characters of words and false otherwise.

Example:

Input: words = ["abc","aabc","bc"]
Output: true
Explanation: Put all the characters in a pool, that is "abc" + "aabc" + "bc" = "aaabbbc".
Then we can use the characters to create "abc", "abc", and "abc".

Clarifying Questions

1. What does it mean to make all strings equal?
   • It means after redistributing all characters, each word in the list should end up as the same string.
2. Can the strings contain any characters?
   • For simplicity, we assume lower-case alphabets only.
3. What should be returned?
   • Return true if it’s possible to redistribute the characters to make all strings in the list identical, otherwise false.

Strategy

1. Counting Characters:
   • We will count the frequency of each character across all strings.
2. Checking Divisibility:
   • For each character that appears, its total count should be divisible by the length of the list words. If all characters satisfy this condition, then it’s possible to redistribute them equally, otherwise, it’s not.

Code

def make_equal(words):
    from collections import Counter
    
    # Calculate the frequency of each character in all strings combined
    total_char_count = Counter()
    
    for word in words:
        total_char_count.update(word)
    
    # Check if each character count is divisible by the number of words
    num_words = len(words)
    
    for count in total_char_count.values():
        if count % num_words != 0:
            return False
    
    return True

# Example usage:
words = ["abc","aabc","bc"]
print(make_equal(words))  # Output: True

Time Complexity

• Counting Frequencies:
  • Each string is traversed once to update the Counter. If n is the total number of characters across all strings and k is the number of strings, this step takes O(n) time.
• Checking Divisibility:
  • We iterate over the unique characters (at most 26 for lower-case alphabets), so this takes O(1) time in the worst case.

Thus, the overall time complexity is O(n) where n is the total number of characters across all strings.

Conclusion

By counting the frequencies of each character and ensuring each character’s total count is divisible by the number of strings, we can determine if it is possible to redistribute the characters to make all strings equal. This method ensures efficient processing and checks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?