Minimum Characters For Words

Tags

Minimum Characters For Words

Category

Strings

Difficulty

Medium

Problem Statement

Given an array of words, find the minimum set of characters needed such that you can spell every word in the array. If a character appears multiple times in a single word, you need at least that many copies of that character. The result should account for the maximum frequency of each character across all words.

Intuition

For each word, we need a certain frequency of each character. To be able to spell every word, we need enough of each character to cover the word that uses it the most. This means we take the maximum frequency of each character across all words.

Approach

  1. Initialize a global frequency map to track the maximum count of each character needed.
  2. For each word in the input array: a. Count the frequency of each character in the word. b. For each character, update the global map to be the maximum of the current global count and this word's count.
  3. Convert the global frequency map into a list of characters, repeating each character according to its maximum frequency.
  4. Return this list.

Pseudocode

function minimumCharactersForWords(words):
    globalMaxFreq = {}
    for each word in words:
        wordFreq = countCharacters(word)
        for each (char, count) in wordFreq:
            globalMaxFreq[char] = max(globalMaxFreq[char], count)

    result = []
    for each (char, count) in globalMaxFreq:
        add char to result count times
    return result

Time & Space Complexity

  • Time: O(n * k) where n is the number of words and k is the maximum length of a word. We count characters in each word and update the global map.
  • Space: O(c) where c is the number of unique characters across all words. The output list size is the sum of all maximum frequencies.

Key Insights

  • The problem reduces to finding the element-wise maximum of character frequency vectors across all words.
  • This is essentially the same logic as finding the Least Common Multiple of multisets.
  • Each character's required count is independent of other characters, so we can compute them separately.

Edge Cases

  • Empty array of words: return an empty list.
  • Words with repeated characters: e.g., "aab" requires two 'a's and one 'b'.
  • All identical words: the frequency is just that of one word.
  • Single-character words: each unique character appears at least once.
  • Words with no overlapping characters: the result is the union of all characters.

Linked mentions