1255. Maximum Score Words Formed by Letters

[mah-shamim]

Discussed in #263

^{Originally posted by mah-shamim August 9, 2024}
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.

[mah-shamim]

The problem is about maximizing the score of valid words formed using a given set of letters. The words can only be used once, and each letter in the list can be used at most as many times as it appears in the list. The score for each word is determined by the sum of the scores of its individual characters. We aim to find the maximum score obtainable from any combination of valid words formed.

Key Points

1. Words and Letters: You are given a list of words and a set of available letters.
2. Score Mapping: Each letter has an associated score between 0 and 10 (inclusive). The score of each word is the sum of the scores of its characters.
3. Valid Word Formation: Each word must be formed using the available letters, without exceeding the letter counts in the list.
4. Maximizing the Score: We need to compute the maximum score by selecting any combination of words that can be formed from the given letters.

Approach

• Bitmasking: Since the number of words is small (<=14), we can iterate over all subsets of words using bitmasking. Each subset corresponds to a combination of words. There are 2^n subsets, where n is the number of words.

• Counting Letters: For each subset of words, we need to check if we can form those words with the available letters. We can maintain a frequency count of letters in the list and ensure that we don't exceed the available count for any letter.

• Score Calculation: For each valid combination of words, calculate the total score by summing the scores of the characters in those words.

Plan

1. Count Available Letters: Create a frequency count for the available letters in the list.
2. Iterate Over All Word Subsets: For each subset of words, calculate the letter frequency required and check if it’s valid.
3. Calculate Score: If the subset is valid, compute the score for the words in that subset.
4. Track Maximum Score: Keep track of the maximum score encountered.

Let's implement this solution in PHP: 1255. Maximum Score Words Formed by Letters

<?php
/**
 * @param String[] $words
 * @param String[] $letters
 * @param Integer[] $score
 * @return Integer
 */
function maxScoreWords($words, $letters, $score) {
    $letterCounts = array_fill(0, 26, 0); // Array to hold counts of each letter in 'letters'

    // Count the occurrence of each letter in 'letters'

    foreach ($letters as $letter) {

        $letterCounts[ord($letter) - ord('a')]++;
    }

    $numWords = count($words); // Total number of words
    $maxScore = 0; // Variable to store the maximum score

    // Loop through all combinations of words

    for ($combination = 0; $combination < (1 << $numWords); ++$combination) {

        $wordCounts = array_fill(0, 26, 0); // Current letter counts for the current combination of words

        // Build the count for the current combination

        for ($wordIndex = 0; $wordIndex < $numWords; ++$wordIndex) {

            // Check if the word at wordIndex is included in the current combination

            if ($combination >> $wordIndex & 1) {

                // If so, count each letter in the word

                foreach (str_split($words[$wordIndex]) as $letter) {

                    $wordCounts[ord($letter) - ord('a')]++;
                }

            }

        }

        $isValidCombination = true; // Flag to check if the combination is valid
        $currentScore = 0; // Score for the current combination

        for ($letterIndex = 0; $letterIndex < 26; ++$letterIndex) {

            // If any letter count exceeds what is available, the combination is invalid

            if ($wordCounts[$letterIndex] > $letterCounts[$letterIndex]) {

                $isValidCombination = false;
                break; // No need to continue if the combination is invalid
            }

            // Calculate score for the current combination

            $currentScore += $wordCounts[$letterIndex] * $score[$letterIndex];
        }

        // If the combination is valid and the score is higher than the maximum found so far, update maxScore

        if ($isValidCombination && $maxScore < $currentScore) {

            $maxScore = $currentScore;
        }
    }

    // Return the maximum score possible with the given words and letters
    return $maxScore;

}

// Example usage:
$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];
echo maxScoreWords($words, $letters, $score) . "\n"; // Output: 23

$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];
echo maxScoreWords($words, $letters, $score) . "\n"; // Output: 27

$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];
echo maxScoreWords($words, $letters, $score) . "\n"; // Output: 0
?>

Explanation:

1. Letter Count: For each word, we calculate how many times each letter appears. We need to ensure that the combined letter counts for any subset of words don't exceed the available counts from the letter list.

2. Subset Generation: We generate subsets of words using bitmasking. For each subset, we check if it's possible to form the words in that subset with the available letters. If it's possible, we calculate the score and update the maximum score if necessary.

3. Score Calculation: For each valid subset, the score is calculated by adding the scores of individual letters in the words of that subset.

Example Walkthrough

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]

• Step 1: Count the occurrences of letters:

  letterCounts = [2, 0, 1, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] // for a to z

• Step 2: Generate subsets of words and check if they can be formed with the available letters:

  • For subset ["dad", "good"], we calculate the letter counts needed:

    wordCounts = [2, 0, 1, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    This is valid because the letter counts do not exceed the available letters.

• Step 3: Calculate the score for this valid subset:

  score = 5 + 1 + 5 + 3 + 2 + 2 + 5 = 23

• Step 4: Update the maximum score. The final result is 23.

Time Complexity

• Generating subsets: There are 2ⁿ subsets, where n is the number of words.
• Checking each subset: For each subset, we need to calculate the letter counts, which takes O(w) time, where w is the maximum length of a word.
• Total Complexity: The total time complexity is O(2ⁿ × w), which is feasible given n ≤ 14.

Output for Example 1

maxScoreWords(["dog", "cat", "dad", "good"], ["a", "a", "c", "d", "d", "d", "g", "o", "o"], [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

This approach efficiently computes the maximum score of any valid combination of words using bitmasking and dynamic checking of letter counts. The use of subsets ensures that we examine all possible combinations of words, while the letter counting ensures we only consider valid word formations.