Problem of The Day: Maximum Score Words Formed by Letters

Problem Statement

Intuition

To solve this problem, the goal is to maximize the score of words we can form using given letters. Each word has a score, and we can only use each letter a limited number of times. This problem can be approached using a combination of backtracking and bit manipulation to explore all possible combinations of words efficiently.

Approach

Word Scoring: First, we compute the score for each word individually if it can be formed with the given letters. This is done by checking if the word can be formed with the available letters and summing up the scores for the letters in the word.

Depth-First Search (DFS): We use DFS to explore all possible combinations of words that can be formed. For each combination, we check if the words can be formed with the available letters and update the maximum score if the current combination yields a higher score.

Backtracking: During the DFS, we use backtracking to explore both the scenarios of including a word in the current combination and not including it. This ensures that all possible combinations are considered.

Validation: We validate if a word can be formed with the remaining letters at each step of the DFS to ensure we are only considering valid combinations.

Complexity

• Time complexity: O(2^n) where n is the number of words. This is because we are considering all subsets of the words

• Space complexity: O(n) where n is the depth of the recursion stack used for DFS

Code

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        word_score = defaultdict(int)
        for word in words:
            curr_score = 0
            counter = Counter(letters)
            for c in word:
                counter[c] -= 1
                if counter[c] < 0:
                    curr_score = 0
                    break
                else:
                    index = ord(c) - ord('a')
                    curr_score += score[index]

            word_score[word] = curr_score

        self.res = 0
        counter = Counter(letters)

        def isValid(word):
            letter_freq = Counter(word)
            for c in word:
                if letter_freq[c] > counter[c] or c not in counter:
                    return False
            return True

        def dfs(i, curr, curr_score, word_list):
            if i == len(word_list):
                return
            if isValid(curr):
                self.res = max(self.res, curr_score)
            if i + 1 < len(word_list):
                dfs(i + 1, curr + word_list[i + 1], curr_score + word_score[word_list[i + 1]], word_list)
            dfs(i + 1, curr, curr_score, word_list)

        for i in range(len(words)):
            words[i], words[0] = words[0], words[i]
            dfs(0, words[0], word_score[words[0]], words)
            words[i], words[0] = words[0], words[i]


        return self.res

Editorial Solution

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        W = len(words)
        # Count how many times each letter occurs
        self.max_score = 0
        freq = [0 for i in range(26)]
        subset_letters = [0 for i in range(26)]
        for c in letters:
            freq[ord(c) - 97] += 1

        # Check if adding this word exceeds the frequency of any letter
        def is_valid_word(subset_letters):
            for c in range(26):
                if freq[c] < subset_letters[c]:
                    return False
            else:
                return True

        def check(w, words, score, subset_letters, total_score):
            if w == -1:
                # If all words have been iterated, check the score of this subset
                self.max_score = max(self.max_score, total_score)
                return
            # Not adding words[w] to the current subset
            check(w - 1, words, score, subset_letters, total_score)
            # Adding words[w] to the current subset
            L = len(words[w])
            for i in range(L):
                c = ord(words[w][i]) - 97
                subset_letters[c] += 1
                total_score += score[c]

            if is_valid_word(subset_letters):
                # Consider the next word if this subset is still valid
                check(w - 1, words, score, subset_letters, total_score)

            # Rollback effects of this word
            for i in range(L):
                c = ord(words[w][i]) - 97
                subset_letters[c] -= 1
                total_score -= score[c]

        check(W - 1, words, score, subset_letters, 0)
        # Return max_score as the result
        return self.max_score