LeetCode Solutions Blog

Maximum Score Words Formed by Letters

Difficulty: Hard

Problem Description

Given a list of words, a list of single letters (which might be repeating), and a score for every character, return the maximum score of any valid set of words formed by using the given letters. Each word can only be used once, and it is not necessary to use all characters in the letters.

Key Insights

Each word's score is calculated based on the sum of the scores of its constituent letters.
The letters can be used only once, and we need to ensure that the combination of words does not exceed the available letters.
The problem can be approached using backtracking or dynamic programming to explore all combinations of words.

Space and Time Complexity

Time Complexity: O(2^N * M), where N is the number of words and M is the average length of the words.
Space Complexity: O(N + L), where N is the number of words and L is the number of letters.

Solution

This problem can be solved using a backtracking approach. We will use a recursive function to explore all combinations of words, keeping track of the letters used and their remaining counts. A score variable will accumulate the maximum score obtained.

Create a frequency count of the available letters.
For each word, check if it can be formed with the remaining letters.
If it can, calculate the score of that word and recursively attempt to form more words with the remaining letters.
Keep track of the maximum score encountered during this process.

Code Solutions

from collections import Counter

def maxScoreWords(words, letters, score):
    letter_count = Counter(letters)
    
    def can_form(word, count):
        word_count = Counter(word)
        for char in word_count:
            if word_count[char] > count[char]:
                return False
        return True

    def calculate_score(word):
        return sum(score[ord(char) - ord('a')] for char in word)

    def backtrack(index, count):
        if index == len(words):
            return 0
        
        # Option 1: Skip the current word
        max_score = backtrack(index + 1, count)
        
        # Option 2: Include the current word if possible
        if can_form(words[index], count):
            # Update the letter count
            for char in words[index]:
                count[char] -= 1
            
            # Calculate the score including this word
            current_score = calculate_score(words[index])
            max_score = max(max_score, current_score + backtrack(index + 1, count))
            
            # Revert the letter count
            for char in words[index]:
                count[char] += 1

        return max_score

    return backtrack(0, letter_count)

# 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]
print(maxScoreWords(words, letters, score))  # Output: 23