LeetCode Solutions Blog

Maximum Score Words Formed by Letters

Number: 1381

Difficulty: Hard

Paid? No

Problem Description

Given a list of words, a collection of letters (with possible repetitions) and an array representing the score for each letter, the goal is to form any valid combination of words so that the total score is maximized. Each word can be used at most once and each letter from the given collection can be used only once. The score for a word is the sum of scores for each character in the word.

Key Insights

Precompute the frequency count and score for each word.
Use backtracking to explore all possible subsets of the words.
At each step, decide whether to include a word if the current available letter frequencies allow it.
Update the maximum score among all valid combinations.
Since the maximum number of words is limited (<= 14), the exponential solution is acceptable.

Space and Time Complexity

Time Complexity: O(2^n * m) where n is the number of words and m is the average length of a word, due to exploring all subsets. Space Complexity: O(n) for the recursion call stack and additional space for frequency arrays.

Solution

We use a backtracking approach where we try to include or exclude each word. Before including a word, we check if we have sufficient letters in our current frequency count to form it. If yes, we subtract the counts for that word, update the running score and continue the recursion. Then we backtrack by adding back the counts. This approach leverages recursion (or DFS) to examine every possible combination of words and capture the highest possible total score.

Code Solutions

# Function to compute maximum score words
def maxScoreWords(words, letters, score):
    # Precompute available letter frequencies from letters list.
    available = [0] * 26
    for ch in letters:
        available[ord(ch) - ord('a')] += 1

    # Precompute frequency and score for each word.
    wordFreqs = []
    wordScores = []
    for word in words:
        freq = [0] * 26
        wordScore = 0
        for ch in word:
            idx = ord(ch) - ord('a')
            freq[idx] += 1
            wordScore += score[idx]
        wordFreqs.append(freq)
        wordScores.append(wordScore)

    # Use backtracking to explore all subsets
    def backtrack(index, currentScore, available):
        if index == len(words):
            return currentScore
        # Option 1: Skip current word
        maxScore = backtrack(index + 1, currentScore, available)
        # Option 2: Include current word if possible
        canUse = True
        for i in range(26):
            if wordFreqs[index][i] > available[i]:
                canUse = False
                break
        if canUse:
            # Subtract counts for the selected word
            for i in range(26):
                available[i] -= wordFreqs[index][i]
            # Recursively obtain score including this word
            maxScore = max(maxScore, backtrack(index + 1, currentScore + wordScores[index], available))
            # Backtrack: restore letter counts
            for i in range(26):
                available[i] += wordFreqs[index][i]
        return maxScore

    return backtrack(0, 0, available)


# 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))  # Expected output: 23