mediumSliding Window

Permutation in String

## Problem

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 the substring of `s2`.

Examples

Input

s1 = "ab", s2 = "eidbaooo"

Output

true

"ba" is a permutation of "ab" and is a substring of s2.

Input

s1 = "ab", s2 = "eidboaoo"

Output

false

No permutation of "ab" appears in s2.

Constraints

1 <= s1.length, s2.length <= 10^4 s1 and s2 consist of lowercase English letters.

Python