algoadvance

Leetcode 1897. Redistribute Characters to Make All Strings Equal

Problem Statement

Given an array of strings words, determine if it is possible to redistribute the characters in words so that every string in words is equal. All words must contain the exact same characters in the same quantities after redistribution.

Clarifying Questions

• What is the minimum length of a word in the array?
  • Each word has at least one character.
• What is the maximum length of a word in the array, and how many words can words contain?
  • Each word has a length between 1 and 1000, and the total number of words in the array is between 1 and 1000.
• Are the characters limited to lowercase alphabets?
  • Yes, only lowercase English letters are considered.

Strategy

To solve this problem, we need to check whether we can reorganize the characters such that every word becomes the same. Here is the approach:

1. Count the total frequency of each character in the entire list of words.
2. For each character count, check if it can be evenly divided by the number of words.
   • This ensures that each character can be evenly distributed across all words.

Code

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

bool makeEqual(vector<string>& words) {
    unordered_map<char, int> charCount;
    
    int numWords = words.size();
    
    // Count the total occurrences of each character in all the words
    for (const string& word : words) {
        for (char ch : word) {
            charCount[ch]++;
        }
    }
    
    // Check if each character count is divisible by the number of words
    for (const auto &entry : charCount) {
        if (entry.second % numWords != 0) {
            return false;
        }
    }
    
    return true;
}

Time Complexity

• Counting Characters: We iterate through all characters in all words, which is O(N * M) where N is the number of words and M is the maximum length of a word.
• Checking Divisibility: We check divisibility for each unique character, which is O(1) since the number of unique characters is constant (26 for lowercase English letters).

Overall, the time complexity is O(N * M). This should be efficient given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?