Permutation in String
MediumSliding Window
Given two strings s1 and s2, return True if s2 contains a contiguous substring that is a rearrangement (permutation) of s1, and False otherwise.
A substring is a rearrangement of s1 when it has exactly the same length and exactly the same count of every letter as s1; only the order may differ. Note that s1 itself counts as one of its own rearrangements.
Example 1
- Input:
- s1 = "abc", s2 = "cbxbac"
- Output:
- True
- Explanation
- The length-3 windows of
s2arecbx,bxb,xbaandbac. The last one has onea, oneband onec, so it is a rearrangement ofabc.
Example 2
- Input:
- s1 = "aab", s2 = "abbxab"
- Output:
- False
- Explanation
- No length-3 window has two
acharacters (the windows areabb,bbx,bxa,xab), so the answer isFalseeven thoughabappears.
Example 3
- Input:
- s1 = "abcd", s2 = "abc"
- Output:
- False
- Explanation
s1is longer thans2, so no window ofs2is long enough.
Constraints
- 1 ≤
s1.length,s2.length≤ 104 s1ands2contain only lowercase English letters