1255. Maximum Score Words Formed By Letters - Explanation

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def can_form_word(w, letter_cnt):
            word_cnt = Counter(w)
            for c in word_cnt:
                if word_cnt[c] > letter_cnt[c]:
                    return False
            return True

        def get_score(w):
            res = 0
            for c in w:
                res += score[ord(c) - ord('a')]
            return res

        letter_cnt = Counter(letters)

        def backtrack(i):
            if i == len(words):
                return 0

            res = backtrack(i + 1)  # skip
            if can_form_word(words[i], letter_cnt):  # include (when possible)
                for c in words[i]:
                    letter_cnt[c] -= 1
                res = max(res, get_score(words[i]) + backtrack(i + 1))
                for c in words[i]:
                    letter_cnt[c] += 1

            return res

        return backtrack(0)

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        letter_cnt = [0] * 26
        for c in letters:
            letter_cnt[ord(c) - ord('a')] += 1

        n = len(words)
        word_scores = [0] * n
        word_freqs = [[0] * 26 for _ in range(n)]

        for i, word in enumerate(words):
            for c in word:
                idx = ord(c) - ord('a')
                word_freqs[i][idx] += 1
                word_scores[i] += score[idx]

        def backtrack(i):
            if i == n:
                return 0

            res = backtrack(i + 1)  # skip
            can_include = all(word_freqs[i][j] <= letter_cnt[j] for j in range(26))

            if can_include:  # include (when possible)
                for j in range(26):
                    letter_cnt[j] -= word_freqs[i][j]
                res = max(res, word_scores[i] + backtrack(i + 1))
                for j in range(26):
                    letter_cnt[j] += word_freqs[i][j]

            return res

        return backtrack(0)

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        letter_cnt = [0] * 26
        for c in letters:
            letter_cnt[ord(c) - ord('a')] += 1

        n = len(words)
        word_scores = [0] * n
        word_freqs = [[0] * 26 for _ in range(n)]

        for i, word in enumerate(words):
            for c in word:
                idx = ord(c) - ord('a')
                word_freqs[i][idx] += 1
                word_scores[i] += score[idx]

        res = 0

        for mask in range(1 << n):
            cur_score = 0
            cur_letter_cnt = letter_cnt[:]
            valid = True

            for i in range(n):
                if mask & (1 << i):
                    for j in range(26):
                        if word_freqs[i][j] > cur_letter_cnt[j]:
                            valid = False
                            break
                    if not valid:
                        break

                    for j in range(26):
                        cur_letter_cnt[j] -= word_freqs[i][j]

                    cur_score += word_scores[i]

            if valid:
                res = max(res, cur_score)

        return res