Maximum Score Words Formed by Letters Interview Question for Meta

def maxScoreWords(words, letters, score):
    letter_counts = {}
    for letter in letters:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    def calculate_score(word):
        word_score = 0
        for char in word:
            word_score += score[ord(char) - ord('a')]
        return word_score

    def is_valid(word, current_counts):
        for char in word:
            if current_counts.get(char, 0) == 0:
                return False
        return True

    def backtrack(index, current_counts):
        if index == len(words):
            return 0

        # Option 1: Skip the current word
        max_score = backtrack(index + 1, current_counts)

        # Option 2: Include the current word if possible
        word = words[index]
        if is_valid(word, current_counts):
            word_score = calculate_score(word)
            new_counts = current_counts.copy()
            for char in word:
                new_counts[char] -= 1

            max_score = max(max_score, word_score + backtrack(index + 1, new_counts))

        return max_score

    return backtrack(0, letter_counts)


# 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

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

Explanation:

This Python code calculates the maximum score achievable by forming words from a given list of words using a limited set of letters and their corresponding scores.

maxScoreWords(words, letters, score) Function: This is the main function that takes the list of words, the list of available letters, and the score for each letter as input.
letter_counts Dictionary: It initializes a dictionary called letter_counts to store the frequency of each letter in the letters list. This helps in efficiently checking whether a word can be formed using the available letters.
calculate_score(word) Function: This helper function calculates the score of a given word by summing up the scores of its individual characters based on the score list provided. It uses the ASCII value of each character to find its corresponding score.
is_valid(word, current_counts) Function: This helper function checks if a given word can be formed using the letters available in the current_counts dictionary. It ensures that there are enough occurrences of each character in the word to form it.
backtrack(index, current_counts) Function: This is the core recursive function that explores all possible combinations of words to find the one with the maximum score. It uses a backtracking approach.
- Base Case: If the index reaches the end of the words list, it means all words have been considered, and it returns 0.
- Recursive Step:
  - It first considers the option of skipping the current word (not including it in the combination) and recursively calls itself with the next index.
  - Then, it checks if the current word can be formed using the available letters. If it can, it calculates the score of the word and recursively calls itself with the next index and updated letter counts.
  - It takes the maximum of these two options (either skip the word or include it) to determine the maximum score achievable from this point onwards.
Return Value: The maxScoreWords function initiates the backtracking process by calling the backtrack function with an initial index of 0 and the letter_counts dictionary, and returns the maximum score found.

Big(O) Runtime Analysis:

The runtime complexity of the solution is primarily determined by the backtrack function, which explores all possible combinations of words.

There are n words, where n is the number of words in the input list.
For each word, there are two choices: either include it or skip it.
Therefore, the total number of possible combinations is 2^n.
For each combination, the is_valid function is called, which iterates through the characters of the word. The length of the words is limited to 15, so this contributes a factor of O(15) which is essentially O(1).
Therefore, the overall runtime complexity is O(2^n), where n is the number of words.

Big(O) Space Usage Analysis:

The space complexity is determined by the depth of the recursion stack and the space used to store the letter_counts dictionary.
The maximum depth of the recursion stack is n, where n is the number of words.
The letter_counts dictionary stores the frequency of each letter in the letters list. The number of distinct letters is at most 26 (the number of letters in the English alphabet).
Therefore, the space complexity is O(n + 26), which simplifies to O(n), where n is the number of words.