1255. Maximum Score Words Formed by Letters
Tags: php, leetcode, algorithms, programming
Published: 2024-05-24 19:42:23

1255\. Maximum Score Words Formed by Letters

Hard

Given a list of `words`, list of  single `letters` (might be repeating) and `score` of every character.

Return the maximum score of **any** valid set of words formed by using the given letters (`words[i]` cannot be used two or more times).

It is not necessary to use all characters in `letters` and each letter can only be used once. Score of letters `'a'`, `'b'`, `'c'`, `...` ,`'z'` is given by `score[0]`, `score[1]`, `...` , `score[25]` respectively.

**Example 1:**

- **Input:** 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]
- **Output:** 23
- **Explanation:** 

  Score  a=1, c=9, d=5, g=3, o=2

  Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.

  Words "dad" and "dog" only get a score of 21.

**Example 2:**

- **Input:** 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]
- **Output:** 27
- **Explanation:** 

  Score  a=4, b=4, c=4, x=5, z=10

  Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.

  Word "xxxz" only get a score of 25.

**Example 3:**

- **Input:** 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]
- **Output:** 0
- **Explanation:** 

  Letter "e" can only be used once.

**Constraints:**

- <code>1 <= words.length <= 14</code>
- <code>1 <= words[i].length <= 15</code>
- <code>1 <= letters.length <= 100</code>
- <code>letters[i].length == 1</code>
- <code>score.length == 26</code>
- <code>0 <= score[i] <= 10</code>
- `words[i]`, `letters[i]` contains only lower case English letters.

**Solution:**

```
class Solution {

    /**
     * @param String[] $words
     * @param String[] $letters
     * @param Integer[] $score
     * @return Integer
     */
    function maxScoreWords($words, $letters, $score) {
        $letterCounts = array_fill(0, 26, 0);
        foreach ($letters as $letter) {
            $letterCounts[ord($letter) - ord('a')]++;
        }

        $numWords = count($words);
        $maxScore = 0;
        
        for ($combination = 0; $combination < (1 << $numWords); ++$combination) {
            $wordCounts = array_fill(0, 26, 0);
            for ($wordIndex = 0; $wordIndex < $numWords; ++$wordIndex) {
                if ($combination >> $wordIndex & 1) {
                    foreach (str_split($words[$wordIndex]) as $letter) {
                        $wordCounts[ord($letter) - ord('a')]++;
                    }
                }
            }

            $isValidCombination = true;
            $currentScore = 0;

            for ($letterIndex = 0; $letterIndex < 26; ++$letterIndex) {
                if ($wordCounts[$letterIndex] > $letterCounts[$letterIndex]) {
                    $isValidCombination = false;
                    break;
                }
                $currentScore += $wordCounts[$letterIndex] * $score[$letterIndex];
            }
            
            if ($isValidCombination && $maxScore < $currentScore) {
                $maxScore = $currentScore;
            }
        }
        
        return $maxScore;
    }
}
```


**Contact Links**

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**