Sorting every window to find anagrams

This function returns the start indices of every substring of s that is an anagram of p (lowercase letters, |s| = 3·10⁴, |p| up to 3·10⁴). It is correct but too slow when p is long. Optimize it to linear time.

1def find_anagrams(s, p):
2    k = len(p)
3    key = sorted(p)
4    out = []
5    for i in range(len(s) - k + 1):
6        if sorted(s[i:i + k]) == key:
7            out.append(i)
8    return out

1. Give the current complexity in terms of n = |s| and k = |p|, and plug in the worst-case sizes.
2. What does "anagram" actually require? Find a representation of a window that is cheaper than a sorted copy.
3. Show how consecutive windows differ and how to update your representation in O(1).
4. Write the O(n) solution and describe how you check equality of the representation without an O(26) comparison per step (optional refinement).