Задача: №30. Substring with Concatenation of All Words
Сложность: hard

Дана строка s и массив строк words, все слова одинаковой длины.
Нужно найти все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке и без повторов).
Верните список индексов, где такие подстроки начинаются.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]

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

1⃣Создать карту частот mapOfWords для слов из words, а также массив arr для подсчета символов всех слов (предварительная фильтрация).

2⃣Использовать скользящее окно длиной totalLen = k * words.length, где k — длина одного слова. На каждом шаге сравнивать текущую подстроку с шаблоном.

3⃣Проверить:
- Совпадают ли символы (arr стал нулевым по всем позициям).
- Можно ли разбить подстроку на слова, соответствующие words, без нарушений частоты и порядка.

😎 Решение:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String, Integer> mapOfWords = new HashMap<>();
        for (String word : words) mapOfWords.put(word, mapOfWords.getOrDefault(word, 0) + 1);

        int k = words[0].length();
        int n = words.length * k;
        int sLen = s.length();
        if (sLen < n) return answer;

        int[] arr = new int[26];
        for (String word : words) {
            for (int i = 0; i < k; i++) {
                arr[word.charAt(i) - 'a']++;
            }
        }

        int start = 0, end = n - 1;
        for (int i = 0; i <= end; i++) arr[s.charAt(i) - 'a']--;

        while (end < s.length() - 1) {
            if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
                answer.add(start);
            }
            arr[s.charAt(start++) - 'a']++;
            arr[s.charAt(++end) - 'a']--;
        }

        if (allZeros(arr) && validWords(s.substring(start, end + 1), new HashMap<>(mapOfWords), k)) {
            answer.add(start);
        }

        return answer;
    }

    public boolean allZeros(int[] arr) {
        return Arrays.stream(arr).allMatch(i -> i == 0);
    }

    public boolean validWords(String s, HashMap<String, Integer> mapOfWords, int k) {
        for (int i = 0; i * k < s.length(); i++) {
            String current = s.substring(i * k, (i + 1) * k);
            if (!mapOfWords.containsKey(current) || mapOfWords.get(current) == 0) return false;
            mapOfWords.put(current, mapOfWords.get(current) - 1);
        }
        return true;
    }
}

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