Count Occurrences of Anagram - Java Solution

1. Introduction

This blog post explores how to count the occurrences of anagrams of a given word within a larger text. An anagram of a word is formed by rearranging its letters. This problem showcases a use case of the sliding window technique in string manipulation.

Problem

Given a word and a text, return the count of occurrences of the anagrams of the word in the text. The anagrams use all the original letters of the word exactly once.

2. Solution Steps

1. Create a frequency map for the letters in the word.

2. Use a sliding window of size equal to the length of the word to traverse the text.

3. Add/remove characters from the frequency map as the window slides.

4. When the frequency map matches that of the word, increment the count.

5. Return the total count.

3. Code Program

import java.util.HashMap;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        System.out.println("Count of anagrams: " + countAnagrams("forxxorfxdofr", "for"));
        System.out.println("Count of anagrams: " + countAnagrams("aabaabaa", "aaba"));
    }

    // Method to count occurrences of anagrams
    public static int countAnagrams(String text, String word) {
        HashMap<Character, Integer> wordMap = new HashMap<>();
        for (char c : word.toCharArray()) {
            wordMap.put(c, wordMap.getOrDefault(c, 0) + 1);
        }

        int count = 0;
        int windowStart = 0;
        int matched = 0;
        HashMap<Character, Integer> windowMap = new HashMap<>();

        // Sliding window technique
        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char rightChar = text.charAt(windowEnd);
            windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);

            if (windowMap.equals(wordMap)) {
                count++;
            }

            // Slide the window
            if (windowEnd >= word.length() - 1) {
                char leftChar = text.charAt(windowStart);
                if (windowMap.get(leftChar) == 1) {
                    windowMap.remove(leftChar);
                } else {
                    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
                }
                windowStart++;
            }
        }
        return count;
    }
}

Output:

Count of anagrams: 3
Count of anagrams: 4

Explanation:

The countAnagrams method applies a sliding window technique to find all the anagrams of a given word in a text. It maintains a hashmap for the frequencies of characters in the current window and compares it with the frequency map of the word. 

For example, in the text "forxxorfxdofr" with the word "for", the method finds three occurrences of the anagrams of "for". 

Similarly, it finds four occurrences in "aabaabaa" for the word "aaba".