algoadvance

Leetcode 1897. Redistribute Characters to Make All Strings Equal

Problem Statement

You are given an array of strings words (each string consists of lowercase English letters).

You need to determine if you can redistribute the characters of words such that every string in the array becomes equal.

Return true if you can achieve this and false otherwise.

Example:

  1. Input: words = [“abc”, “aabc”, “bc”] Output: true Explanation: The strings can be converted into “aabbcc” or “abcabc”.

  2. Input: words = [“ab”, “a”] Output: false Explanation: There is no way to make all strings equal.

Clarifying Questions

  1. Are there any constraints on the length of the strings or the number of strings in the array?
    • Constraints might include:
      • 1 <= words.length <= 1000
      • 1 <= words[i].length <= 100
    • All characters will be lowercase English letters.
  2. Is it necessary to provide an optimal pattern of equal strings, or just a boolean result?
    • We just need to return a boolean indicating if it is possible.

Strategy

  1. Count Characters:
    • First, we will count the frequency of each character in all words combined.
  2. Check Divisibility:
    • For each unique character, check if its total frequency is divisible by the number of strings. If not, it is impossible to redistribute the characters to make all strings equal.
  3. Return Result:
    • If every character’s total count is divisible by the number of strings, return true. Otherwise, return false.

Code

import java.util.*;

public class RedistributeCharacters {
    
    public boolean canRedistribute(String[] words) {
        // Total frequency map for all characters
        Map<Character, Integer> frequencyMap = new HashMap<>();
        
        // Counting frequency of each character in all strings
        for (String word : words) {
            for (char c : word.toCharArray()) {
                frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
            }
        }
        
        int numStrings = words.length;
        
        // Check if we can redistribute characters
        for (int count : frequencyMap.values()) {
            if (count % numStrings != 0) {
                return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        RedistributeCharacters solution = new RedistributeCharacters();
        
        String[] words1 = {"abc", "aabc", "bc"};
        System.out.println(solution.canRedistribute(words1)); // Output: true
        
        String[] words2 = {"ab", "a"};
        System.out.println(solution.canRedistribute(words2)); // Output: false
    }
}

Time Complexity

Overall, the time complexity is O(n \times m), which is efficient given the problem constraints.

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