ASAPUtils
The signal
Two facts in the statement pin down the whole approach:
- A permutation of
s1has exactlys1.lengthcharacters → the window size is fixed. - A permutation is fully described by its character counts → this is frequency counting inside a fixed window.
Two patterns you already know, composed. That composition is most of what medium problems are.
Approach ladder
1. Brute force — O(n · m log m)
Take every substring of length m, sort it, compare to sorted s1. Correct, slow.
2. Count instead of sort — O(n · m)
Same loop, but compare character counts instead of sorted strings. Better, still re-counts each window from scratch.
3. What is it wasting?
Consecutive windows overlap in all but two characters. Recounting the whole window each time throws away everything you just computed — one character enters, one leaves, and only those two counts change.
4. Optimal — slide the counts, O(n)
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) return false;
vector<int> want(26, 0), have(26, 0);
for (char c : s1) want[c - 'a']++;
int k = s1.size();
for (int r = 0; r < (int)s2.size(); r++) {
have[s2[r] - 'a']++;
if (r >= k) have[s2[r - k] - 'a']--;
if (r >= k - 1 && want == have) return true;
}
return false;
}
function checkInclusion(s1, s2) {
if (s1.length > s2.length) return false;
const at = c => c.charCodeAt(0) - 97;
const want = new Array(26).fill(0), have = new Array(26).fill(0);
for (const c of s1) want[at(c)]++;
const k = s1.length;
for (let r = 0; r < s2.length; r++) {
have[at(s2[r])]++;
if (r >= k) have[at(s2[r - k])]--;
if (r >= k - 1 && want.every((v, i) => v === have[i])) return true;
}
return false;
}
5. The truly O(1)-per-step version
Comparing two 26-slot arrays each step is O(26) — constant, but you can do better and interviewers
like seeing it. Keep a matches counter of how many of the 26 letters currently agree, and update
it only for the two letters that changed:
let matches = 0;
for (let i = 0; i < 26; i++) if (want[i] === have[i]) matches++;
// on each slide, before/after changing a letter's count, adjust `matches`
// for just that letter; answer is true when matches === 26.
Complexity
- Time O(n) — one pass, constant work per step.
- Space O(1) — two 26-slot arrays.
Traps
r >= kvsr >= k - 1. The first evicts, the second checks. Swapping them gives windows of the wrong size.- Not guarding
s1.length > s2.length. Reads out of range or loops zero times depending on language. - Comparing JavaScript arrays with
===. Never equal by reference; compare element-wise. - Using a map and comparing sizes. Counts that hit zero must be deleted or the size comparison lies. An array sidesteps this entirely.
Blank re-solve prompt
Return whether s2 contains a permutation of s1. Fixed window, O(n). Then upgrade the comparison from O(26) per step to O(1).