Сумма длинн слов, которые могут быть сформированы из заданного набора букв

Источник: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/

Дан массив строк words и строкаchars.

Страка хорошая, если ее можно составить из символов строки chars (каждый символ может быть использован только раз).

Вернуть сумму длинн все хороших слов из массива words.

Пример 1:

Дано: words = ["cat","bt","hat","tree"], chars = "atach"
Результат: 6
Пояснение: Мы можем сформировать строки "cat" и "hat", поэтому 3 + 3 = 6.

Пример 2:

Дано: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Результат: 10
Пояснение: Мы можем сформировать строки "hello" и "world", поэтому 5 + 5 = 10.

Ограничения:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] и chars состоят из строчных букв английского алфавита
  

 

Идея решения

Идея достаточно примитивна: нужно попробовать собрать каждое слово из массива wordsиз букв слова chars.  Для этого мы считаем частоты букв в слове chars, затем сканируем каждое слово по отдельности и уменьшаем частоту текущей буквы из массива частот. Как только мы встречаем частоту, которая обнулилась и мы не можем использовать эту букву и значит, не можем сконструировать текущее слово. 

Если частот хватило для сборки текущего слова, то прибавляем его длинну к сумме длинн.

Имплементация

class Solution {
    public static int countCharacters(String[] words, String chars) {
        int count = 0;
        int[] seen = new int[26];
        // считаем частоты букв, входящих в строку chars       
        for (char c : chars.toCharArray())
            seen[c - 'a']++;
       
        // сопоставляем подсчитанные частоты с каждым словом из words                    for (String word : words) {
            // делаем копию массива seen
            int[] tSeen = Arrays.copyOf(seen, seen.length);
            int Tcount = 0;
            for (char c : word.toCharArray()) {
                if (tSeen[c - 'a'] > 0) {
                    tSeen[c - 'a']--;
                    Tcount++;
                }
            }
            if (Tcount == word.length())
                count += Tcount;
        }
        return count;
    }
}