Sliding Window — Permutation in String
↗ LeetCode: Permutation in String · Medium · pattern chapter →
Given strings s1 and s2, return true iff s2 contains any permutation of s1 as a substring.
Example 1 — s1 = "ab", s2 = "eidbaooo" → true ("ba" is a permutation of "ab") Example 2 — s1 = "ab", s2 = "eidboaoo" → falseExample 3 — s1 = "adc", s2 = "dcda" → true ("dca" at index 0)
Constraints — 1 ≤ |s1|, |s2| ≤ 10⁴. Lowercase English. Brute compares every window against sorted target — O(n·k·log k) = 10⁴·10⁴·13 ≈ 1.3·10⁹ ops (TLE). Sliding-window frequency compare is O(n·26) = ~2·10⁵ ops.
Interview timer00:00
Approach 1 — Sort every window
Intuition. Slide a window of size |s1| over s2; sort each and compare to sorted s1.
boolean checkInclusionBrute(String s1, String s2) {
int k = s1.length();
if (k > s2.length()) return false;
char[] a = s1.toCharArray();
Arrays.sort(a);
String target = new String(a);
for (int i = 0; i + k <= s2.length(); i++) {
char[] w = s2.substring(i, i + k).toCharArray();
Arrays.sort(w);
if (target.equals(new String(w))) return true;
}
return false;
}Complexity — Time O((n − k) · k log k); Space O(k) per window.
Approach 2 — Fixed window with frequency array
Insight from brute. Sorting is overkill — we just need the multiset. A 26-int frequency count is enough. Compare need[] vs current have[] at every position.
boolean checkInclusionEq(String s1, String s2) {
int k = s1.length();
if (k > s2.length()) return false;
int[] need = new int[26], have = new int[26];
for (char c : s1.toCharArray()) need[c - 'a']++;
for (int i = 0; i < s2.length(); i++) {
have[s2.charAt(i) - 'a']++;
if (i >= k) have[s2.charAt(i - k) - 'a']--;
if (i >= k - 1 && Arrays.equals(need, have)) return true;
}
return false;
}Complexity — Time O((n − k) · 26); Space O(1).
Approach 3 — Running match counter (O(1) per step)
Insight from previous. Arrays.equals costs 26 per position. Maintain a matches counter: for each of the 26 letters, track whether have[c] == need[c]. Increment/decrement matches incrementally on every add/remove.
boolean checkInclusion(String s1, String s2) {
int k = s1.length();
if (k > s2.length()) return false;
int[] need = new int[26], have = new int[26];
for (char c : s1.toCharArray()) need[c - 'a']++;
int matches = 0;
for (int i = 0; i < 26; i++) if (need[i] == 0) matches++;
for (int i = 0; i < s2.length(); i++) {
int r = s2.charAt(i) - 'a';
have[r]++;
if (have[r] == need[r]) matches++;
else if (have[r] == need[r] + 1) matches--;
if (i >= k) {
int l = s2.charAt(i - k) - 'a';
have[l]--;
if (have[l] == need[l]) matches++;
else if (have[l] == need[l] - 1) matches--;
}
if (matches == 26) return true;
}
return false;
}Complexity — Time O(n) — O(1) per position; Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Sort every window | O((n−k) · k log k) | O(k) | brute; correct baseline |
Fixed window + Arrays.equals | O((n−k) · 26) | O(1) | acceptable, since 26 is a constant |
| Running match counter | O(n) | O(1) | polish — mention if asked to justify |
When to use which
- Anagram / multi-set check → fixed window + frequency array is the canonical answer.
- Interviewer asks "can you do without the 26 factor?" → running match counter.
- Unicode alphabet → use
HashMap<Character,Integer>; running-match trick still applies with slightly more bookkeeping. - Return all match indices → this is Find All Anagrams in a String.
Related problems
- Find All Anagrams in a String — return all match positions
- Valid Anagram — single comparison
- Minimum Window Substring — variable-size window with need/have
- Substring with Concatenation of All Words — window on word offsets