← Back to DSA Animator
Permutation in String LC #567 Medium Fixed Sliding Window · Matches Counter
Problem

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.

Example
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: "ba" at index 3 is a permutation of "ab".
Constraints: 1 ≤ s1.length, s2.length ≤ 10⁴  |  s1 and s2 consist of lowercase English letters.
Try Examples
Custom:
Approach
Fixed Sliding Window + Matches Counter
Slide a window of exactly k = s1.length over s2. Track matches: how many s1-chars have have[c] == need[c]. When matches == needed → found a permutation. O(1) per slide — no full array comparison. O(n) time, O(1) space.
① Init
›
② Build Window
›
③ Slide →
›
④ Result
Pattern s1
String s2
matches / needed 0 / 0
Waiting to start…
Char Frequencies — need (s1) vs have (window)
charneedhave
Init
Press ▶ Play or Next Step to begin.
Variables
L (left)
—
R (right)
—
matches
0
k (window)
—
Step Logic
Press ▶ Play or Next Step to begin.
—
—
Ready 0 / 0
Select an example and press Play.
Algorithm
1
Build need map from s1. needed = unique chars in s1.
2
Slide r over s2. Add s2[r] to have. If have[c]==need[c] → matches++
3
When r ≥ k: remove s2[r−k] from have. If was matching → matches--
4
If matches == needed → permutation found at [r−k+1 .. r] → return true
5
After full scan with no match → return false
Time
O(n)
Space
O(1)
Why It Works

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.