Given two strings, s 1 and s 2, return true if s 2 contains some permutation of s 1 as a substring.
DSA Animator › DSA Revision › Strings › Permutation in String
Remember: permutation means equal letter counts. A fixed window updates two counts per step. The video solves Permutation in String (LeetCode 567, Medium) with the Fixed Sliding Window pattern from the Strings topic, and you can replay every step in the interactive Permutation in String animation.
Given two strings, s 1 and s 2, return true if s 2 contains some permutation of s 1 as a substring.
For s 1 equal to a b, and s 2 equal to e i d b a o o o, the answer is true. The substring b a, at index 3, is a permutation of a b.
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.
The counts of s 1 are a 1 and b 1. Window e i: no match. Window i d: no match. Window d b: no match. Window b a: the counts are a 1 and b 1, which match. So the answer is true.
In code, count the letters of s 1, and of the first window. Slide right: add the new letter and remove the one that left. Return true as soon as the two count arrays are equal. Each comparison is 26 checks, so it's O of n time and O of 1 space.
Remember: permutation means equal letter counts. A fixed window updates two counts per step.