Pattern visualizer
Anagram Permutation in String
A permutation of s1 is any rearrangement of its letters, so a matching substring must be exactly as long as s1 and use exactly the same letters, however they are ordered. That means the answer never depends on position inside the window — only on how many of each letter it holds. Count the letters of s1 once, count the first window of that width in s2, then slide the window one step at a time: each step adds the letter entering on the right and removes the one leaving on the left, so re-counting from scratch is never needed and each window costs a constant amount of work. Animated on: s1 = "abc", s2 = "eidbaobca" — does s2 contain a permutation of s1 as a contiguous substring?.
Fixed-width sliding window over letter counts
Looking for any 3-letter stretch of "eidbaobca" that uses exactly the same letters as "abc". Order inside the stretch does not matter, so only the letter COUNTS have to match — that turns the search into one 3-wide window sliding right.
1FUNCTION checkInclusion(s1, s2):2 k <- LENGTH(s1)3 need <- COUNTS(s1)4 win <- COUNTS(s2[0 TO k - 1])5 IF win = need:6 RETURN TRUE7 FOR r <- k TO LENGTH(s2) - 1:8 win[s2[r]] <- win[s2[r]] + 19 win[s2[r - k]] <- win[s2[r - k]] - 110 IF win = need:11 RETURN TRUE12 RETURN FALSE
← / → step · space play · Home restart