Задача: 438. Find All Anagrams in a String
Сложность: medium

Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева.

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

public class Solution {
    public IList<int> FindAnagrams(string s, string p) {
        int ns = s.Length, np = p.Length;
        if (ns < np) return new List<int>();

        var pCount = new Dictionary<char, int>();
        var sCount = new Dictionary<char, int>();

        foreach (char ch in p) {
            if (pCount.ContainsKey(ch)) {
                pCount[ch]++;
            } else {
                pCount[ch] = 1;
            }
        }

        var output = new List<int>();

        for (int i = 0; i < ns; ++i) {
            char ch = s[i];
            if (sCount.ContainsKey(ch)) {
                sCount[ch]++;
            } else {
                sCount[ch] = 1;
            }

            if (i >= np) {
                ch = s[i - np];
                if (sCount[ch] == 1) {
                    sCount.Remove(ch);
                } else {
                    sCount[ch]--;
                }
            }

            if (pCount.SequenceEqual(sCount)) {
                output.Add(i - np + 1);
            }
        }
        return output;
    }
}

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