Permutation In String

Medium · Sliding Window

You are given two strings made of lowercase letters. Determine whether any contiguous block of characters in the second string is exactly some rearrangement of all the characters of the first string. Return true if such a block exists anywhere in the second string, otherwise return false.

Examples

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true
Why:    s2 contains "ba" starting at index 3, which is a rearrangement of s1.

Input:  s1 = "ab", s2 = "eidboaoo"
Output: false
Why:    no contiguous substring of s2 is a rearrangement of the letters in s1.

Input:  s1 = "adc", s2 = "dcda"
Output: true
Why:    the substring "cda" starting at index 1 uses exactly the letters a, d, c.

Constraints

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

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Permutation In String

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Permutation In String. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.