Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is a substring of s2.
We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is a substring of s2.
A medium sliding window problem, graded against 7 test cases (4 of them hidden).
A moving window over a contiguous run, expanding and contracting to hold an invariant.
Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."
More Sliding Window problems →A permutation of `s1` is any window of length `s1.length` in `s2` with identical letter frequencies. Build the frequency table of `s1` and of the first window of `s2`, and count how many of the 26 letters already match. Then slide the window one character at a time: each slide changes the count of exactly two letters (the one entering, the one leaving), so the matches tally can be updated in O(1). The answer is true the moment all 26 letters match.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
These apply to the pattern as a whole, not just this problem.