Decide whether any contiguous block of s2 with the same length as s1 is a rearrangement of s1.
Before you code
Compare letter counts, not orders: two strings are permutations of each other exactly when all their counts match. Slide a fixed-size window across s2 and update two counts per step instead of recounting the whole window.
Hints
- Fix the window size to the length of s1 and compare frequency counts against s1's counts.
- On each shift, add the entering letter and remove the leaving one — recounting the whole window each time would turn the pass quadratic.
- Check the counts after every shift, including the very first window, before sliding past it.
Production & complexity notes
When solving Permutation in String on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Sliding window to reinforce the underlying pattern.
What it practices
Fixed-size windows with count updates, from Sliding window.