Problem

Given a word and a text, return the count of occurrences of the anagrams of the word in the text.

Read Anagram Definition

Examples

Examples 1

1
2
3

Input: text = forxxorfxdofr, word = for
Output : 3
Explanation : Anagrams of the word for - for, orf, ofr appear in the text and hence the count is 3.

Example 2

1
2
3
4

Input : text = aabaabaa, word = aaba
Output : 4
Explanation : Anagrams of the word aaba - aaba, abaa each appear twice in the text and hence the
count is 4.

Solution

Method 1 - Brute Force

We have already seen - Valid Anagram. We can use a “Counting Chars” method with a frequency hashmap for the words.

Simply loop over the text up to size w and check if they are valid anagrams.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

private static int countOccurrenceOfAnagram(String text, String word) {
	int n = text.length();
	int k = word.length();
	int count = 0;

	for(int i = 0; i <= n-k; i++) {
		String window = text.substring(i, i+k);

		if(areAnagrams(window, word)) {
			count++;
		}
	}

	return count;
}

Method 2 - Sliding Window

There are two issues with the above approach:

  1. We calculate the hashmap repeatedly for the word, though we only need to compute it once.
  2. The implementation repeatedly breaks substrings and recalculates character counts.

For example, consider:

1

Input: text = forxxorfxdofr, word = for

In the above method, we first calculate the character count for the substring “for”, then move to the next substring “orx” and recalculate the character count. This leads to redundant work for overlapping substrings like “or”. We can reduce this repetitive work using the sliding window technique.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class Solution {

	public int countOccurrenceOfAnagram(String text, String word) {
        int n = text.length();
        int k = word.length();
        int count = 0;

        // Calculate the count of each character for the given word
        Map<Character, Integer> wordCharCount = new HashMap<>();
        for (int i = 0; i < k; i++) {
            char c = word.charAt(i);
            wordCharCount.put(c, wordCharCount.getOrDefault(c, 0) + 1);
        }

        // Store the character count for the current substring (current window)
        Map<Character, Integer> substrCharCount = new HashMap<>();
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < n; windowEnd++) {
            char c = text.charAt(windowEnd);
            substrCharCount.put(c, substrCharCount.getOrDefault(c, 0) + 1);  // Include next char in window

            if (windowEnd - windowStart + 1 == k) {  // Window size reached
                if (areAnagramsFreqMap(wordCharCount, substrCharCount)) {
                    count++;
                }

                // Remove the start char as we slide the window
                char startChar = text.charAt(windowStart);
                if (substrCharCount.get(startChar) == 1) {
                    substrCharCount.remove(startChar);
                } else {
                    substrCharCount.put(startChar, substrCharCount.get(startChar) - 1);
                }
                windowStart++;  // Slide the window
            }
        }
        
        return count;
    }
    
    // Check if two character count maps are equal
    boolean areAnagramsFreqMap(Map<Character, Integer> word1CharCount, Map<Character, Integer> word2CharCount) {
        for (char c : word1CharCount.keySet()) {
            if (!word1CharCount.get(c).equals(word2CharCount.get(c))) { // Use equals instead of != for Integer comparison
                return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from collections import defaultdict
class Solution:
	def count_occurrence_of_anagram(self, text, word):
	    n = len(text)
	    k = len(word)
	    count = 0
	
	    # Calculate the count of each character for the given word
	    word_char_count = defaultdict(int)
	    for c in word:
	        word_char_count[c] += 1
	
	    # Store the character count for the current substring (current window)
	    substr_char_count = defaultdict(int)
	    window_start = 0
	    
	    for window_end in range(n):
	        c = text[window_end]
	        substr_char_count[c] += 1  # Include the next char in the window
	
	        if window_end - window_start + 1 == k:  # Window size reached
	            if self.are_anagrams_freq_map(word_char_count, substr_char_count):
	                count += 1
	
	            # Remove the start char as we slide the window
	            start_char = text[window_start]
	            if substr_char_count[start_char] == 1:
	                del substr_char_count[start_char]
	            else:
	                substr_char_count[start_char] -= 1
	                
	            window_start += 1  # Slide the window
	    
	    return count
	def are_anagrams_freq_map(self, word1_char_count, word2_char_count):
	    # Check if two character count dictionaries are equal
	    for c in word1_char_count:
	        if word1_char_count[c] != word2_char_count.get(c, 0):
	            return False
	    return True