Pattern visualizer
Count Occurrences of Anagram
An anagram of pat is a rearrangement of its letters, so a matching substring must be exactly as long as pat and hold exactly the same letters however they are ordered. Position inside the window never matters — only how many of each letter it contains. That makes the window a fixed width: count the letters of pat once, count the first window of that width, and then move the window one step at a time. Each move adds the letter arriving on the right and removes the one leaving on the left, so no window is ever recounted from scratch and each of the n - k + 1 windows costs constant work. Count the windows whose letter counts equal pat's and that tally is the answer. Animated on: txt = "cbabcacbab", pat = "abc" — how many substrings of txt are anagrams of pat?.
Fixed-width window over letter counts
Every anagram of "abc" is exactly 3 letters long and uses the same letters in some order, so only a 3-wide window can ever match and only its letter COUNTS matter. Count the letters of "abc" once, then slide that window across all 10 letters of "cbabcacbab" and tally the windows whose counts agree.
1FUNCTION countAnagrams(txt, pat):2 k <- LENGTH(pat)3 need <- COUNTS(pat)4 win <- COUNTS(txt[0 TO k - 1])5 total <- 06 FOR l <- 0 TO LENGTH(txt) - k:7 IF l > 0:8 win[txt[l + k - 1]] <- win[txt[l + k - 1]] + 19 win[txt[l - 1]] <- win[txt[l - 1]] - 110 IF win = need:11 total <- total + 112 RETURN total
← / → step · space play · Home restart