All problems

Permutation in String

Medium · sliding window

You are given two strings of lowercase English letters, s1 and s2.

Decide whether s2 contains a block of consecutive letters that is a rearrangement of s1. That means the block has the same length as s1 and uses exactly the same letters, each one the same number of times, but possibly in a different order. The block may be s2 itself.

Return true if such a block exists and false otherwise. If s1 is longer than s2, the answer is false.

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

The block "ba" at positions 3 and 4 uses one a and one b, just like "ab".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

The letters a and b are both there, but they are never next to each other.

Example 3

Input: s1 = "aab", s2 = "baa"

Output: true

The whole of s2 is a rearrangement of s1.

Constraints

• 1 <= len(s1) <= 10^4
• 1 <= len(s2) <= 10^4
• s1 and s2 consist of lowercase English letters