Topic · Sliding WindowMedium
Permutation in String
Understand the problem
Given two strings s1 and s2. Return true if any permutation of s1 appears as a contiguous substring of s2.
Examples:
ts
s1 = "ab", s2 = "eidbaooo"
output = true // "ba" is a permutation of "ab", found at s2[3..4]
s1 = "ab", s2 = "eidboaoo"
output = false // no permutation of "ab" exists in s2A permutation means: the same set of characters, possibly in a different order.
The problem only considers lowercase letters a-z.
Basic approach
O(n · m log m) time, O(m) space — n=|s2|, m=|s1|ts
function checkInclusion(s1: string, s2: string): boolean {
// The naive idea — generate every permutation of s1 and search for it in s2 —
// is infeasible (|s1|=10 → 10! = 3,628,800). Use this instead: sort each window.
const sorted1 = s1.split('').sort().join('')
for (let i = 0; i <= s2.length - s1.length; i++) {
const window = s2.slice(i, i + s1.length).split('').sort().join('')
if (window === sorted1) return true
}
return false
}Why this approach is slow:
At each position i you must sort a substring of length m → O(m log m).
- Total O(n · m log m).
- This approach does not reuse information from the neighboring window.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.