Permutation in String
Given two strings s1 and s2, decide whether some contiguous substring of s2 is a rearrangement of s1.
- 1 ≤ s1.length, s2.length ≤ 10^4
- Lowercase English letters
- The window length is fixed at
|s1| - Match is about character *counts*, not order
- Compare two 26-entry histograms as the window slides
A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
Build a 26-count histogram of s1 and of the first |s1| characters of s2. Slide the window one step at a time across s2, incrementing the entering character and decrementing the leaving one, and check whether the histograms match. Track the number of positions where the two histograms agree so the check is O(1) instead of O(26) per step.
- Sorting every window is O(n · L log L); it works but the fixed-window count comparison is strictly better.