Permutation Substring Search

You are given two strings, s1 and s2. Your task is to determine whether any substring of s1 is a permutation of s2. That is, check if there exists a contiguous segment in s1 whose characters can be rearranged to form s2.

For example, if s1 = "abcdefg" and s2 = "cde", the answer is True because the substring "cde" from s1 is exactly a permutation of s2. However, if s2 = "hij", then no such permutation exists in s1 and the answer is False.

Note: An empty s2 is considered a valid case and should return True since an empty string is a permutation of itself.

The problem can be formalized as follows: Given two strings, determine if there exists an index i such that the frequency counts of the characters in the substring s1[i : i+|s2|] matches exactly with that of s2. This can be written using the concept of sliding window with the following equality condition using count arrays:

$$\mathrm{count}_{s1}(s1[i:i+|s2|]) = \mathrm{count}_{s2}(s2) \quad \text{for some} \; i. $$

inputFormat

The input is read from standard input (stdin) as two lines:

• The first line contains the string s1.
• The second line contains the string s2.

outputFormat

Output a single line to standard output (stdout) containing either True if any permutation of s2 is a substring of s1, or False otherwise.

## sample

abcdefg
cde

True

</p>