Count Anagram Substrings

You are given two lowercase strings s and p. Count how many substrings of s are anagrams of p, that is, count the number of starting positions in s at which the |p| characters that follow can be rearranged to exactly form p (matching every letter's frequency).

Input: The first line contains the string s. The second line contains the string p. Output: Print a single integer: the number of substrings of s that are anagrams of p.

1 <= |p| <= |s| <= 10^5 s and p consist only of lowercase English letters.

This is the sliding-window sibling of 'Group Anagrams' and 'Anagram Check' from the Hashing category - all three rely on the same core insight that anagram-equality reduces to frequency-array equality, just applied in different contexts (grouping, single-pair checking, or windowed counting).

Count how many substrings of a string are anagrams of a given pattern. Brute force: For every window position, sort both the window's characters and p's characters and compare - this costs O(n * k log k), unnecessary when frequency arrays can be compared directly without sorting. Optimised: Maintaining a running frequency array for the current window (updated incrementally as it slides, adding incoming and removing outgoing characters) avoids ever re-counting the whole window from scratch - comparing two fixed-size (26-element) frequency arrays for equality is O(26), effectively O(1), making the whole scan O(n) instead of O(n*k).

1. Build a frequency array of the |p| characters in p, and maintain a frequency array of the CURRENT window of s (of the same length). 2. Slide the window one character at a time: ADD the incoming character's frequency and REMOVE the outgoing character's frequency. 3. Two frequency arrays represent an anagram match exactly when they're EQUAL element-for-element; compare them once per window position.

Time: O(n * 26) which simplifies to O(n), since comparing two 26-element frequency arrays is a small constant amount of work per window. Space: O(1) - the frequency arrays are always exactly 26 elements, regardless of string length.

Handle the case where |p| == |s| (there is exactly one substring to check) and the case where no substring of s matches (answer is 0).

Be ready to mention the alternative of tracking just a SINGLE 'number of matching frequency positions' counter (updated incrementally) instead of comparing full 26-element arrays every time - a further optimization that avoids even the small constant-factor array comparison.