Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. In other words, check if any contiguous substring of s2 is an anagram of s1.
For example, given s1 = "ab" and s2 = "eidbaooo", the output is true because s2 contains "ba" which is a permutation of "ab". Given s1 = "ab" and s2 = "eidboaoo", the output is false.
Explain your approach, how you efficiently compare character frequencies, and analyze complexity.
How to approach it
- Hint 1
A permutation of s1 has the same character frequencies as s1. You need to find a window in s2 with matching frequencies.
- Hint 2
Use a fixed-size sliding window of length equal to s1 over s2.
- Hint 3
Maintain a frequency count for the window. When a character enters, increment its count. When one leaves, decrement. Compare with s1's frequency count.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.