Contains Permutation

Given two strings s and pattern, determine whether any permutation of pattern exists as a contiguous substring within s.

A permutation of a string is defined as any rearrangement of its letters. For instance, if pattern = "abc", then any of "abc", "acb", "bac", "bca", "cab", or "cba" is a valid permutation. Formally, if n is the length of pattern, then you need to decide if there exists an index i in s such that the substring s[i...i+n-1] is a permutation of pattern.

The problem can be stated using the formula:

\( \exists i,\ 0 \le i \le |s|-|pattern|\) such that \(\text{Counter}(s[i...i+|pattern|-1]) = \text{Counter}(pattern)\).

Note: An empty pattern is considered to be a permutation of itself, so if pattern is empty, the answer should be True.

inputFormat

The input consists of two lines:

• The first line contains the string s.
• The second line contains the string pattern.

outputFormat

Output a single line containing True if any permutation of pattern exists as a substring in s, otherwise output False.

oidbcaf
abc

True