Count Occurrences of Anagrams

Fixed-width window over letter counts

time O(n)space O(1)

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.

Details

Animated on: txt = "cbabcacbab", pat = "abc" — how many substrings of txt are anagrams of pat?

Problem:Count Occurrences of AnagramsMedium

Fixed-width window over letter counts

step 1 / 10

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

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.

Pseudocode

1FUNCTION countAnagrams(txt, pat):
2  k <- LENGTH(pat)
3  need <- COUNTS(pat)
4  win <- COUNTS(txt[0 TO k - 1])
5  total <- 0
6  FOR l <- 0 TO LENGTH(txt) - k:
7    IF l > 0:
8      win[txt[l + k - 1]] <- win[txt[l + k - 1]] + 1
9      win[txt[l - 1]] <- win[txt[l - 1]] - 1
10    IF win = need:
11      total <- total + 1
12  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 10 steps

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.
The first window "cba" covers indices 0 to 2. Its counts are exactly the ones "abc" needs, so this is an anagram — the tally rises to 1.
Dropping 'c' off the left and taking 'b' in on the right turns the window into "bab" without recounting anything. It holds 2 'b' where "abc" needs 1, so it is not an anagram and the tally stays at 1.
Dropping 'b' off the left and taking 'c' in on the right turns the window into "abc" without recounting anything. Its counts are exactly the ones "abc" needs, so this is an anagram — the tally rises to 2.
Dropping 'a' off the left and taking 'a' in on the right turns the window into "bca" without recounting anything. Its counts are exactly the ones "abc" needs, so this is an anagram — the tally rises to 3.
Dropping 'b' off the left and taking 'c' in on the right turns the window into "cac" without recounting anything. It holds 0 'b' where "abc" needs 1, so it is not an anagram and the tally stays at 3.
Dropping 'c' off the left and taking 'b' in on the right turns the window into "acb" without recounting anything. Its counts are exactly the ones "abc" needs, so this is an anagram — the tally rises to 4.
Dropping 'a' off the left and taking 'a' in on the right turns the window into "cba" without recounting anything. Its counts are exactly the ones "abc" needs, so this is an anagram — the tally rises to 5.
Dropping 'c' off the left and taking 'b' in on the right turns the window into "bab" without recounting anything. It holds 2 'b' where "abc" needs 1, so it is not an anagram and the tally stays at 5.
Every one of the 8 possible windows has been checked in a single left-to-right pass, and 5 of them (starting at 0, 2, 3, 5, 6) were anagrams of "abc". Return 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Occurrences of Anagrams in the editor All Sliding Window problems Back to roadmap