Count Occurrences of Anagram
A medium Sliding Window problem included in Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Sliding Window
- Sheets
- 1
- Core for
- 5 roles
- Platform
- GeeksforGeeks
The problem
Given a string and a pattern, count the number of anagrams of the pattern that appear as substrings in the string.
Example 1
- Input
- s = "cbaebabacd", p = "abc"
- Output
- 2
- Why
- The anagrams of 'abc' found are 'cba' at index 0 and 'bac' at index 6.
Example 2
- Input
- s = "abab", p = "ab"
- Output
- 3
- Why
- The anagrams of 'ab' found are 'ab', 'ba', and 'ab'.
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
- s and p consist of lowercase English letters
How to think about it
Updated 2026-09-09An anagram has the exact same character frequency counts and the exact same length as the pattern. Because the length is fixed, the window size never changes: slide a fixed-size frame of length p.length across s, adding the incoming character and subtracting the outgoing character.
Approaches, worst first
Sort each substring
time O(n * m log m) · space O(m)
Extract every substring of length p.length from s, sort its characters, and compare with the sorted pattern. Sorting each window introduces unnecessary logarithmic overhead.
Fixed-size window with array comparison
time O(26 * n) · space O(1)
Slide a window of size m, updating a 26-element frequency array on each shift and comparing all 26 frequencies against pattern counts.
Fixed window with match counterWrite this one
time O(n) · space O(1)
Track the count of characters whose frequencies currently match between window and pattern. Adjust matches as characters enter and leave, signaling an anagram whenever matches reach 26.
Where people lose marks · 3
- Failing to handle the case where pattern length exceeds string length, which should immediately return 0.
- Comparing strings directly instead of comparing character frequencies or match tallies.
- Forgetting to evict the leftmost character once the window size surpasses the length of the pattern.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
What each operation costs
| Operation | Time |
|---|---|
| slide window across full array length | O(n) |
| update running aggregate per incoming element | O(1) |
| auxiliary window frequency map storage | O(k) |
What usually goes wrong with Sliding Window
- Shrinking the left border using an if statement instead of a while loop, allowing invalid window conditions to persist across iterations.
- Updating optimum results before validating window legality, recording illegal states that contain duplicate items or violate length requirements.
- Forgetting to decrement left element frequencies or remove empty keys from tracking maps when advancing the left boundary forward.
Which roles need this problem
Sliding Window is a core topic for these 5 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 10 more roles, including SDE / Backend Engineer, Data Engineer, ML Engineer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Sliding Window problems
Problem set and role mapping as of .