🚩 Задача с собеса

Задача: дана строка s и строка p. Необходимо найти все начальные индексы подстрок в s, которые являются анаграммами строки p.

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

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]

Объяснение:
Подстрока с индекса 0 - "cba", анаграмма "abc".
Подстрока с индекса 6 - "bac", анаграмма "abc".

Оптимальное решение использует технику скользящего окна с подсчетом частот символов.

1. Подсчитываем количество и частоту всех символов в строке p
2. Создаем скользящее окно размером со строку p в строке s
3. Для каждой позиции окна сравниваем частоты символов с эталоном
4. При совпадении добавляем индекс в результат

Код:

public class Solution 
{
    public IList<int> FindAnagrams(string s, string p) 
    {
        List<int> result = new List<int>();
        
        if (s.Length < p.Length) 
            return result;
        
        // Массивы для подсчета частот символов (26 букв английского алфавита)
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        
        // Подсчитываем частоты в строке p и первом окне
        for (int i = 0; i < p.Length; i++) 
        {
            pCount[p[i] - 'a']++;
            windowCount[s[i] - 'a']++;
        }
        
        // Проверяем первое окно
        if (AreEqual(pCount, windowCount))
            result.Add(0);
        
        // Скользим окном по строке s
        for (int i = p.Length; i < s.Length; i++) 
        {
            // Добавляем новый символ справа
            windowCount[s[i] - 'a']++;
            
            // Удаляем старый символ слева
            windowCount[s[i - p.Length] - 'a']--;
            
            // Проверяем текущее окно
            if (AreEqual(pCount, windowCount))
                result.Add(i - p.Length + 1);
        }
        
        return result;
    }
    
    // Вспомогательный метод для сравнения массивов частот
    private bool AreEqual(int[] arr1, int[] arr2) 
    {
        for (int i = 0; i < 26; i++) 
        {
            if (arr1[i] != arr2[i])
                return false;
        }
        return true;
    }
}

🐸 Библиотека шарписта

#dotnet_challenge