Permutation in String

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.