Найти все анаграммы в строке

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

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

Пример 1:

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".

Пример 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

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

• 1 <= s.length, p.length <= 3 * 104
• s и p состоят из строчных английских букв.

Решение —

Но если вы внимательно пронаблюдаете, о чем говорит вопрос, вы обнаружите это. В строке от «a до z» присутствует строчный английский алфавит.

Поскольку диапазон указан, нет необходимости использовать HashMap. Потому что в HashMap любой символ присутствует ч/б «a-z». Ему все равно, и он даст вам ответ за O(N).
Но мы дали это, символы из «a-z», we won't use HashMap there is much better way to solve this problem.

Что мы сделаем, так это создадим 2 массива. Массив1 для строки s и Массив2 для строки p. И их размер будет 26. что они хранят частоту строки s и строки p.

• Наша первая задача — сохранить частоту строки p.
• Таким образом, a count — это 1 раз, когда мы обновляем частоту a в массиве, b count — это 1 раз, когда мы обновляем частоту b в массиве и c, а количество равно 1 разу, когда мы обновляем частоту c в массиве. If let's say есть еще c, в дальнейшем мы изменим его частоту до 2.
• Длина "p" равна 3, мы сохраним ее длину, скажем, в переменной "m", и тем самым мы возьмем 3 символа из строки "s" и обновим их частота в массиве 1 (с)

Теперь мы сравним оба массива размером 26! Они равны? Да, они равны с одинаковой частотой появления одного и того же символа. Таким образом, it's an anagram at index 0

• Теперь, что мы будем делать, создадим 2 указателя. 1-й указатель синего цвета в 0-м индексе, работа которого заключается в исключении [уменьшении] частоты. 2-й указатель красного цвета в 3-м индексе, работа которого состоит в том, чтобы включать [приращение] частоты.

• Тем самым мы создадим постоянное окно 3 размера
• Теперь мы добавим «e» и удалим «c» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. Это не анаграмма.

• Теперь мы добавим «b» и удалим «b» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. это не анаграмма

• Теперь мы добавим «а» и удалим «а» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. это не анаграмма

• Теперь мы добавим «b» и удалим «e» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. Это не анаграмма.

• Теперь мы добавим «a» и удалим «b» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. Это не анаграмма.

• Теперь мы добавим «c» и удалим «a» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Так что да, они равны. It's an anagram & we get it from index 6

• Теперь мы добавим «d» и удалим «b» из массива и обновим их частоту. И на каждом этапе мы должны сравнивать, равны ли они? Значит, они не равны. Это не анаграмма.

• Now we will stop. Когда красный указатель выходит за пределы массива.

И общая анаграмма, которую мы нашли, равна [ 0, 6 ]
Итак, мы нашли ее без использования HashMap. In Временная сложность BigO(N).

Я надеюсь, вы поняли, давайте закодируем это!!

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        if(p.length() > s.length()) return  list; // Base Condition
       
            int N=s.length(); // Array1 of s
            int M=p.length(); // Array2 of p
            int[]count = freq(p); // intialize only 1 time
            
            int[]currentCount = freq(s.substring(0, M)); // freq function, update every-time according to sliding window
            
            if(areSame(count,currentCount)) // areSame function
                list.add(0);
        
            int i;
            for(i=M;i<N;i++){ // going from 3 to 9 in above example
                currentCount[s.charAt(i-M) - 'a']--; // blue pointer, decrement frequency
                currentCount[s.charAt(i)-'a']++; // red pointer, increment frequency
                if(areSame(count,currentCount)){ // now check, both array are same
                    list.add(i-M+1); // if we find similar add their index in our list
                }
            }
        return list;
    }
    private boolean areSame(int[] x, int[] y){
        for(int i = 0; i < 26; i++){
            if(x[i] != y[i]) // compare all the frequency & doesnn't find any di-similar frequency return true otherwise false
                return false;
        }
        
        return true;
    }
  private int[] freq(String s){
        int[] count = new int[26]; // create array of size 26
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++; // update acc. to it's frequency
        }
        
        return count; // and return count 
    }
}