Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте функцию для вычисления оценки слова.

2⃣Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов.
Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв.

3⃣Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.

😎 Решение:

import java.util.*;

public class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int maxScore = 0;
        Map<Character, Integer> letterCount = new HashMap<>();
        for (char ch : letters) {
            letterCount.put(ch, letterCount.getOrDefault(ch, 0) + 1);
        }

        for (int i = 1; i < (1 << words.length); i++) {
            int currScore = 0;
            Map<Character, Integer> usedLetters = new HashMap<>();
            boolean valid = true;
            for (int j = 0; j < words.length; j++) {
                if ((i & (1 << j)) != 0) {
                    for (char ch : words[j].toCharArray()) {
                        usedLetters.put(ch, usedLetters.getOrDefault(ch, 0) + 1);
                        if (usedLetters.get(ch) > letterCount.getOrDefault(ch, 0)) {
                            valid = false;
                            break;
                        }
                        currScore += score[ch - 'a'];
                    }
                }
                if (!valid) break;
            }
            if (valid) {
                maxScore = Math.max(maxScore, currScore);
            }
        }

        return maxScore;
    }
}

Ставь 👍 и забирай 📚 Базу знаний