Permutation in String
Problem
Return true if s2 contains some permutation of s1 as a substring — a window of s2 with exactly the same character counts as s1.
Example 1
Input: s1 = "ab", s2 = "eidbaooo" Output: true
"ba".
Example 2
Input: s1 = "ab", s2 = "eidboaoo" Output: false
Test cases
Case 1
Input: "ab", "eidbaooo" Expected: true
Case 2
Input: "ab", "eidboaoo" Expected: false
Case 3
Input: "adc", "dcda" Expected: true
View solutionHide solution1 approach
1. Fixed window of counts
Time O(|s2|)Space O(26)
Slide a window of length |s1| over s2 and compare the 26 counts. Track how many letters match to make each step O(1).
function checkInclusion(s1, s2) { if (s1.length > s2.length) return false; const need = new Array(26).fill(0), win = new Array(26).fill(0); const idx = (c) => c.charCodeAt(0) - 97; for (let i = 0; i < s1.length; i++) { need[idx(s1[i])]++; win[idx(s2[i])]++; } let matches = 0; for (let i = 0; i < 26; i++) if (need[i] === win[i]) matches++; for (let r = s1.length; r < s2.length; r++) { if (matches === 26) return true; for (const [c, d] of [[idx(s2[r]), 1], [idx(s2[r - s1.length]), -1]]) { if (win[c] === need[c]) matches--; win[c] += d; if (win[c] === need[c]) matches++; } } return matches === 26;}Comparing the two 26-arrays on every step is also O(26·n) and is fine to present first.