Permutation in String Visualizer & Step-by-Step Algorithm Solution

Slide a window of length s1.length over s2 and compare letter frequencies to find a permutation.

Category: sliding-window | Difficulty: Medium

Tags: String, Hash Table, Two Pointers, Sliding Window

Permutation in String

s2 · search for a contiguous permutation
e
0
i
1
d
2
b
3
a
4
o
5
o
6
o
7
s1 · target letters (order does not matter)
a
0
b
1
100%
state
m2
n8
Pattern Length
1/33
Explanation

m = 2. A permutation uses exactly these 2 letters with the same frequencies, in any order.

Source Code
1function checkInclusion(s1: string, s2: string): boolean {
2 const m = s1.length;
3 if (m > s2.length) return false;
4 const target = new Array<number>(26).fill(0);
5 const window = new Array<number>(26).fill(0);
6 for (const ch of s1) {
7 target[ch.charCodeAt(0) - 97]++;
8 }
9 for (let right = 0; right < s2.length; right++) {
10 window[s2.charCodeAt(right) - 97]++;
11 if (right >= m) {
12 window[s2.charCodeAt(right - m) - 97]--;
13 }
14 if (right >= m - 1 && target.every((count, i) => count === window[i])) {
15 return true;
16 }
17 }
18 return false;
19}