Sliding Window

Count Occurrences of Anagram

Rajeev SinghAlgorithms1 mins read

Count Occurrences of Anagram

Problem Statement

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

An anagram of a word is a word that’s formed by rearranging the letters of the original word. For example: the anagrams of the word for are

  • for
  • fro
  • ofr
  • orf
  • rof
  • rfo

Note that, the anagrams use all the original letters exactly once.

Examples 1

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

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

A simple approach is to:

  • Iterate over the text
  • Consider each substring of length equal to the length of the given word, and then check if this substring is an anagram of the given word or not.
  • To check if a substring is an anagram of the original word, we can just check if the substring contains all the characters of the word or not.

Efficiently check if two words are anagrams of each other

Two words are anagrams of each other if the count of every character in both the words are same.

We can use a hashmap (Map<Character, Integer>) to store the count of each character in the original word. This will help us easily check if a substring of the text is an anagram of the given word in O(n) time complexity.

Let’s look at the implementation:


public class CountOccurrencesOfAnagram {
    // Two words are anagrams of each other if the count of every character in both the words are same.
    private static boolean isAnagram(Map<Character, Integer> word1CharCount, Map<Character, Integer> word2CharCount) {
        for(char c : word1CharCount.keySet()) {
            if(word1CharCount.get(c) != word2CharCount.get(c)) {
                return false;
            }
        }
        return true;
    }

    private static 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);
        }

        for(int i = 0; i <= n-k; i++) {
            // Find the substring starting from i with length equal to the length of the word. 
            // Calculate its char count to easily determine if it is an anagram of the word or not.
            Map<Character, Integer> substrCharCount = new HashMap<>();
            for(int j = i; j < i+k; j++) {
                char c = text.charAt(j);
                substrCharCount.put(c, substrCharCount.getOrDefault(c, 0)+1);
            }

            // Check if the current substring is an anagram of the given word
            if(isAnagram(wordCharCount, substrCharCount)) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        String text = keyboard.next();
        String word = keyboard.next();
        keyboard.close();

        System.out.printf("Count of occurrences of anagram = %d%n", countOccurrenceOfAnagram(text, word));
    }
}

Sliding Window

If you carefully observe the above implementation, you will notice that we are doing some repetitive work in the inner loop that calculates substrCharCount.

Let’s look at an example

Input: text = forxxorfxdofr, word = for

In the above approach, we first calculate the character count for the substring for, then we move to the next substring orx and calculate the character count again. While doing so, we’re doing repetitive work for the overlapping substring or. We can reduce the repetitive work using the sliding window pattern.

Here is the complete example:


public class CountOccurrencesOfAnagram {
    // Two words are anagrams of each other if the count of every character in both the words are same.
    private static boolean isAnagram(Map<Character, Integer> word1CharCount, Map<Character, Integer> word2CharCount) {
        for(char c : word1CharCount.keySet()) {
            if(word1CharCount.get(c) != word2CharCount.get(c)) {
                return false;
            }
        }
        return true;
    }

    private static 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);
        }

        // Stores the characrer 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 the next char in the window

            if(windowEnd-windowStart+1 == k) { // We've hit the window size. Calculate result and Slide the window
                if(isAnagram(wordCharCount, substrCharCount)) {
                    count++;
                }

                // Reduce count for the char at windowStart since we are sliding the window now
                substrCharCount.put(text.charAt(windowStart), substrCharCount.get(text.charAt(windowStart)) - 1);
                windowStart++; // Slide the window ahead
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        String text = keyboard.next();
        String word = keyboard.next();
        keyboard.close();

        System.out.printf("Count of occurrences of anagram = %d%n", countOccurrenceOfAnagram(text, word));
    }
}