Given two strings s and p, find all the start indices of p's anagrams in s.

The optimal solution uses the Sliding Window technique along with character frequency counting.

First, the frequency of each character in string p is stored in an array. A window of size p.length() is then moved across string s. As characters enter and leave the window, their frequencies are updated accordingly.

Whenever the frequency counts of the current window match the frequency counts of p, the starting index of that window is added to the result list.

This approach avoids sorting every substring and significantly improves performance.

Java Solution:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAllAnagrams {

    public static List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<>();

        if (s.length() < p.length()) {
            return result;
        }

        int[] patternFrequency = new int[26];
        int[] windowFrequency = new int[26];

        for (int index = 0; index < p.length(); index++) {
            patternFrequency[p.charAt(index) - 'a']++;
            windowFrequency[s.charAt(index) - 'a']++;
        }

        if (Arrays.equals(patternFrequency, windowFrequency)) {
            result.add(0);
        }

        for (int right = p.length(); right < s.length(); right++) {

            windowFrequency[s.charAt(right) - 'a']++;

windowFrequency[ s.charAt(right - p.length()) - 'a'

            ]--;

            if (Arrays.equals(patternFrequency, windowFrequency)) {
                result.add(right - p.length() + 1);
            }
        }

        return result;
    }

    public static void main(String[] args) {

        String s = "cbaebabacd";
        String p = "abc";

        List<Integer> result = findAnagrams(s, p);

        System.out.println(result);
    }
}

Output: [0, 6]

Explanation: The substrings "cba" and "bac" are anagrams of "abc", starting at indices 0 and 6 respectively.

Time Complexity: O(n), where n is the length of string s. The sliding window moves through the string only once, and frequency comparison is performed on a fixed-size array of 26 characters.

Space Complexity: O(1), because the frequency arrays have a constant size of 26 regardless of the input size.

Key Interview Points: • Sliding Window is the standard approach for substring matching problems. • Frequency arrays provide faster comparisons than sorting substrings repeatedly. • Sorting every window would result in O(n × k log k) complexity, where k is the length of p. • This problem is a common variation of permutation and anagram matching questions in interviews.