Has Substring Anagram

Return true if the string s contains any substring that is an anagram of part (a contiguous block of len(part) characters with the same letter counts). Assume lowercase letters only.

hasSubstringAnagram(s, part)

Input format: s | part.

Examples

s="cbaebabacd", part="abc"   // → true   ("cba" and "bac")
s="hello", part="xyz"        // → false
s="aa", part="aaa"           // → false  (part longer than s)

Walkthrough

Thinking it through

An anagram of part is any rearrangement of its letters — so a substring of s is an anagram exactly when it has the same length and the same letters the same number of times, regardless of order. That reframes the problem: instead of permutations, you only need to compare letter counts.

Why brute-force sorting is wasteful

A natural first idea: for every substring of length len(part), sort its characters and compare to sorted part. Sorting each window costs O(k log k) for k = len(part), across roughly n positions — O(n · k log k). Worse, most characters in one window are still present in the next; sliding by one only swaps a single character, but a full re-sort throws that shared structure away.

Counting instead of sorting

Since only order-independent frequency matters, track how many of each letter the current window contains, and compare to part's letter-count profile. Comparing two frequency tables (fixed size — 26 lowercase letters) is O(1), not O(k log k).

Making the window slide incrementally

The window has a fixed width of len(part), so the sliding-window trick applies directly: as it moves one step right, one character leaves on the left and one enters on the right. Increment the entering letter's count and decrement the leaving one's, instead of rebuilding the table from scratch.

Building the approach

Build a frequency table for part once, up front.
Slide a window of width len(part) across s, maintaining its own frequency table.
Whenever the window's table matches part's, return true immediately.
If you slide through all of s without a match, return false.

Why this works and scales well

Since you only add or remove one character per step and compare two small fixed-size tables, the whole scan is O(n) with O(1) extra space (bounded by the alphabet, not k or n). This is the string cousin of the fixed sum/product window pattern: consecutive windows overlap almost entirely, so update the summary incrementally instead of recomputing it.

main.py

Auto-saved

Console

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