Count Substring Anagrams

Return how many substrings of s are anagrams of part. Each starting position counts separately. Assume lowercase letters only.

countSubstringAnagrams(s, part)

Input format: s | part.

Examples

s="cbaebabacd", part="abc"   // → 2
s="abab", part="ab"          // → 3   ("ab", "ba", "ab")
s="aa", part="aaa"           // → 0

Walkthrough

Thinking it through

This is the counting version of "does s contain an anagram of part": instead of stopping at the first match, tally every starting position whose window is a rearrangement of part. The underlying comparison is identical to the yes/no version — only difference is you keep scanning and count every match.

Why you shouldn't recompute frequencies from scratch

Building a fresh frequency table for each of the roughly n windows costs O(k) per table (k = len(part)), O(n·k) overall. But adjacent windows overlap in all but one character. Rebuilding from scratch on every slide ignores that overlap.

The incremental window

Maintain one running frequency table for the current window:

Increment the count for the character that just entered on the right.
Decrement the count for the character that just left on the left.
Compare the updated table to part's — a fixed-size comparison (26 letters), O(1) regardless of string length.

Every successful comparison is an anagram — increment your count. Checking every window (rather than stopping early) naturally handles overlapping matches, since the problem counts each valid starting position separately.

Why this is efficient

Each slide does constant work — one increment, one decrement, one fixed-size comparison — so scanning the whole string costs O(n), versus O(n·k) brute force. Space stays O(1), bounded by the alphabet size.

The general lesson

When a problem asks you to evaluate the same property across every fixed-size window, and windows overlap heavily, don't recompute from scratch — maintain a running summary and update it incrementally. Whether you stop at the first hit or count every hit is a small change on the same core technique.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.