{x}
blog image

Maximum Score Words Formed by Letters

Given a list of words, list of  single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

 

Example 1:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.

 

Constraints:

  • 1 <= words.length <= 14
  • 1 <= words[i].length <= 15
  • 1 <= letters.length <= 100
  • letters[i].length == 1
  • score.length == 26
  • 0 <= score[i] <= 10
  • words[i], letters[i] contains only lower case English letters.

Solution Explanation: Maximum Score Words Formed by Letters

This problem asks to find the maximum score achievable by selecting words from a given list, subject to letter frequency constraints. The solution presented uses bit manipulation and a greedy approach to efficiently explore all possible word combinations.

Approach:

The core idea is to represent each possible subset of words as a bitmask. Each bit in the bitmask corresponds to a word in the words list. If the bit is set (1), the word is included in the subset; otherwise (0), it's excluded.

  1. Letter Frequency Count: First, we count the frequency of each letter in the letters array using a Counter (Python) or a simple array (other languages). This allows for quick verification of whether a word combination is feasible.

  2. Binary Enumeration: We iterate through all possible bitmasks from 0 to 2n - 1, where n is the number of words. Each bitmask represents a unique subset of words.

  3. Word Combination Check: For each bitmask, we construct a Counter (or array) to track the letter frequencies in the selected words. We check if the frequency of each letter in this subset is less than or equal to the available letters counted in step 1. If this condition is met, the word combination is valid.

  4. Score Calculation: If the combination is valid, we calculate its score by summing the scores of the individual letters used, weighted by their respective scores provided in the score array.

  5. Maximum Score Tracking: We keep track of the maximum score encountered so far and update it whenever a higher-scoring valid combination is found.

Time Complexity Analysis:

  • The outer loop iterates through all possible bitmasks (2n, where n is the number of words).
  • Inside the loop, constructing the letter frequency counter takes O(M * k), where M is the maximum length of a word and k is the number of selected words. Checking the validity takes O(26) (checking 26 letters). Calculating the score takes O(26).
  • Therefore, the overall time complexity is O(2n * M * k), which is dominated by the exponential term 2n. However, since n (number of words) is limited to 14, this approach remains feasible.

Space Complexity Analysis:

The space complexity is dominated by the frequency counters (cnt and cur), which use O(26) space. The space used by the bitmask is negligible. Therefore, the overall space complexity is O(1).

Code Examples (with minor optimizations):

The provided code examples are already quite efficient. One minor optimization could be to pre-calculate the score of each word to avoid redundant calculations within the main loop. This wouldn't change the overall time complexity but could lead to a slight performance improvement. However, for the given constraints, this optimization is probably not crucial.

The code examples clearly demonstrate the implementation of the described algorithm in Python, Java, C++, and Go. The comments within the code further explain the steps involved in each language.