Problem No 3
Count pattern occurrences with a sliding window
Easy≈ 10 minute session
Lesson guide
What this Python exercise practices
Count pattern occurrences with a sliding window is a beginner practice lesson that focuses on dsa, problem patterns, edge cases. It is designed to be solved in about 10 minutes with examples, starter code, and test feedback.
Prerequisites
- Python functions
- Loops
- Lists
- Basic edge cases
Difficulty and time
- Level
- Beginner
- Estimated time
- 10 minutes
Related public exercises
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
Example 1
Input
s = "cbaebabacd", p = "abc"
Output
2
Explanation
Substrings 'cba' (index 0) and 'bac' (index 6) are anagrams of 'abc'.
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
Sample input 0
count_pattern_occurrences("abab", "ab")
Sample output 0
3
Explanation 0
Substrings are 'ab', 'ba', 'ab'.
AI assistant
Ask me anything!
Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.
Chat history is temporary and will not be saved.
Free preview includes 1 Teach Theory response and 1 AI hint per unlocked preview lesson.