Count pattern occurrences with a sliding window

Summary

Count how many substrings of a text are anagrams of a given pattern using a sliding window.

Problem statement

Given two strings s and p, return the number of substrings in s that are anagrams of p. An anagram of p is any permutation of p. If p is empty or len(p) > len(s), return 0. Use a sliding window and frequency counting to achieve O(n) time.

Task

Given text s and pattern p, count the number of substrings in s that are permutations (anagrams) of p using frequency comparison with a sliding window in O(n) time.

Examples

Input format

Two string arguments: count_pattern_occurrences(s, p)

Output format

Return an integer count of substrings of s that are anagrams of p.

Constraints

0 <= len(s), len(p) <= 10^5. Only lowercase/uppercase letters are not assumed; handle arbitrary characters. Aim for O(n) time and O(k) space where k is character variety.

Samples