Find All Anagrams in a String

Given a string s and a string p, return all starting indices of p's anagrams in s. Strings contain only lowercase English letters.

Use a sliding window of size len(p) with character counts.

Function signature

func FindAnagrams(s string, p string) []int

Inputs / outputs

• s: search string.
• p: pattern string.
• Return: slice of starting indices where an anagram of p begins.

Example

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

Anagrams at "cba" and "bac".

Constraints

• 0 <= len(s), len(p) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

An anagram has the same 26-letter counts. Slide a fixed window over s and compare counts with p.

Invariant: the window length is len(p) and the counts reflect exactly the window.

Algorithm (step-by-step)

1. If len(p) > len(s), return empty slice.
2. Build count arrays for p and the first window of s.
3. If counts match, record index 0.
4. Slide the window:
   • Add new right character.
   • Remove old left character.
   • If counts match, record the new left index.
5. Return the list of indices.

Correctness sketch

• Invariant: the window length is len(p) and the counts reflect exactly the window.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

Trace (hand walkthrough)

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

Anagrams at "cba" and "bac".

Walk:
- window "cba" at 0 matches -> add 0
- slide: "bae" (1), "aeb" (2), "eba" (3), "bab" (4), "aba" (5) no match
- window "bac" at 6 matches -> add 6

Pitfalls to avoid

• Returning indices for windows of the wrong size.
• Forgetting to handle empty p (define behavior; here it returns empty).

Complexity

• Time: O(n)
• Extra space: O(1) (26 counts).

Implementation notes (Go)

• Maintain a frequency diff array and a match count.
• Slide the window and record indices when all counts match.