You are given two strings s and p of lowercase letters. Count the number of start indices i (0-indexed) such that the substring of s beginning at i with length len(p) is a permutation of p — that is, it uses exactly the same multiset of letters as p.
Windows may overlap, and each qualifying start index is counted once. If len(p) > len(s), the answer is 0.
Line 1: the string s (lowercase letters, no spaces).
Line 2: the string p (lowercase letters, no spaces).
A single integer: the number of qualifying start indices.
a-zExample 1
Input
cbaebabacd abc
Expected
2
Explanation
The windows starting at index 0 ('cba') and index 6 ('bac') are both permutations of 'abc'. No other window qualifies, so the count is 2.
Example 2
Input
aaa aa
Expected
2
Explanation
Both length-2 windows 'aa' (at indices 0 and 1) are permutations of 'aa', so the count is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →