LeetCode 567 ·
Medium
Permutation in String
Return true if s2 contains a permutation of s1 as a substring.
Try it
Step through the core mechanic. The simulator below runs the sliding window shape this problem is built on.
Interactive · Fixed-window walkthrough Max sum of k consecutive elements
0
2
L
1
1
2
5
R
3
1
4
3
5
2
6
8
7
1
8
4
init window [0..2], sum = 8
window sum8 best8 k3
Why this is O(n).
Each slide adds one element on the right, drops one on the left — O(1) per
step, n - k slides total. The naive approach recomputes
sum(window)
on every iteration; that's O(n × k). Incremental update is the lever.The approach
Fixed window of length |s1| over s2. Keep a 26-count and a matched counter; the window is a permutation when all 26 counts agree. Update matched at the boundary so each step is O(1).
| Aspect | Value |
|---|---|
| Pattern | Sliding window |
| Recognise it by | A fixed-size window whose letter counts match a pattern. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.