Given strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. In other words, return true if any anagram of s1 exists as a contiguous substring of s2.
s1 = "ab", s2 = "eidbaooo"trues2
need map from s1. needed = unique chars in s1.have. If have[c]==need[c] → matches++have. If was matching → matches--Fixed window = fixed size anagram: A permutation of s1 must have exactly the same character frequencies as s1, in a window of exactly k = s1.length. So we check every k-length window.
matches counter trick: Instead of comparing full frequency arrays at each step (O(26)), we track matches — how many unique chars in s1 satisfy have[c] == need[c]. Only 2 updates per slide (add right, remove left). O(1) per step.
Why over-count hurts: If have[c] > need[c], that char is not matched (extra copies break the anagram). The matches counter only fires when counts are exactly equal — catching both under and over counts.
Generating every permutation of s 1 is factorial time. Sorting every window of s 2 and comparing is also slow.
A permutation has exactly the same letter counts. So slide a window of length s 1 across s 2, and compare letter counts. Each slide only changes two counts: one letter in, one letter out.
Permutation means equal letter counts. A fixed window updates two counts per step.
Run the animation above on your own input, or watch the 1:19 video explanation of Permutation in String with a dry run and Java code.