Problem Statement

Given two strings s and p, return all start indices of p’s anagrams in s. You may return the answer in any order.

An anagram is a rearrangement of letters. For example, "abc" and "cab" are anagrams.

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

• Substring "cba" at index 0 is an anagram of "abc".
• Substring "bac" at index 6 is an anagram of "abc".

Example 2:
Input: s = "abab", p = "ab"
Output: [0, 1, 2]

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters.

---

Approach in Plain English

1. Since we are looking for all anagrams of p in s, the length of substring we care about is always p.length.
2. Use sliding window technique:
   • Maintain a window of size p.length while iterating through s.
   • Track frequency of characters in p and the current window of s.
3. For each window:
   • If frequency counts match exactly, it’s an anagram → add starting index to result.
4. Use an array of size 26 to store character counts (faster than HashMap).
5. Slide the window:
   • Add new character (right end), remove old character (left end) from window counts.
   • Compare updated counts with p’s counts.

Key idea: Sliding window reduces the problem from O(n * m) (checking every substring) to O(n), where n = s.length.

---

Dry Run Example

Take s = "cbaebabacd", p = "abc".

1. p.length = 3, so window size = 3.
2. Count frequencies in p: a=1, b=1, c=1.
3. Slide the window through s:
   • Window "cba" (indices 0-2):
     • Count: c=1, b=1, a=1 → matches p → add 0 to result.
   • Window "bae" (indices 1-3):
     • Count: b=1, a=1, e=1 → doesn’t match → skip.
   • Window "aeb" (indices 2-4):
     • Count: a=1, e=1, b=1 → doesn’t match → skip.
   • Window "bac" (indices 6-8):
     • Count: b=1, a=1, c=1 → matches p → add 6 to result.
4. Result → [0, 6].

---

Textual Approach

1. Prepare frequency count for p.
2. Use two pointers for sliding window: start and end.
3. Maintain count array for current window.
4. If window size equals p.length:
   • Compare counts → if same, add start to result.
   • Slide the window by moving start forward.
5. Repeat until end reaches end of s.

---

Java Code

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

public class FindAllAnagrams {

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;

        int[] pCount = new int[26];
        int[] windowCount = new int[26];

        // Count frequency of characters in p
        for (char c : p.toCharArray()) {
            pCount++;
        }

        int windowSize = p.length();

        for (int i = 0; i < s.length(); i++) {
            // Add current character to window
            windowCount[s.charAt(i) - 'a']++;

            // Remove leftmost character if window exceeded size
            if (i >= windowSize) {
                windowCount[s.charAt(i - windowSize) - 'a']--;
            }

            // Compare arrays for match
            if (Arrays.equals(pCount, windowCount)) {
                res.add(i - windowSize + 1);
            }
        }

        return res;
    }

    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]
    }
}

---

Key Points

• Sliding window reduces time complexity from O(n * m) to O(n)
  (n = length of s, m = length of p).
• Use frequency arrays of size 26 for lowercase letters.
• Always remove the leftmost character when the window size exceeds p.length.
• Compare arrays efficiently using Arrays.equals.