Check whether any substring of one string is a permutation of another string.
Check Inclusion
gfgProblem
Given two strings s1 and s2, determine whether some substring of s2 is a permutation of s1.
A substring is any contiguous sequence of characters. A permutation means the substring contains exactly the same characters with the same frequencies as s1, but in any order.
Return true if such a substring exists; otherwise return false.
Clarification
You do not need to return the substring itself, only whether at least one valid window exists.
Input Format
- Two strings
s1ands2 - Characters are typically lowercase English letters in the standard version of this problem
Output Format
- Return a boolean value
trueif some substring ofs2is a permutation ofs1falseotherwise
Constraints
1 <= len(s1), len(s2)- In the common formulation, both strings contain only lowercase English letters
- A linear or near-linear solution is expected
Example 1
Input
s1 = "ab" s2 = "eidbaooo"
Output
true
Explanation
The substring "ba" appears in s2 and is a permutation of s1. Thus the answer is true.
Example 2
Input
s1 = "ab" s2 = "eidboaoo"
Output
false
Explanation
No substring of s2 has exactly the same character frequencies as s1.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.