public class FindMaxSumOfAllSubArraysOfSizeK {

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 2, 9, 7, 1};
        int k = 3;

        int max = solve(arr, k);
        // ans should be 18 for sub-array {2, 9, 7} as this is the maximum sum for any sub-array for given size k
        System.out.println(max);
    }

    private static int solve(int[] arr, int k) {

        // pointers to maintain start and end of the sliding window
        int left = 0, right = 0;
        // variable to hold the answer
        int ans = Integer.MIN_VALUE;
        // sum to hold the sum of current on-going window
        int sum = 0;

        // while we have not reached till the end
        while (right < arr.length) {
            // add current right value to sum
            sum += arr[right];
            // if not reached the size of sliding window
            // just increase the right side
            if (right - left + 1 < k) {
                right++;
            } else if (right - left + 1 == k) { // once we have reached the size of sliding window, we need to increase both the variables, but need addition logic
                // first find the answer till now to hold the maxSum so far for the sub-arrays
                ans = Math.max(ans, sum);
                // as we are going to slide, so we reduce the sum of the left most element from sum variable
                sum -= arr[left];
                // finally increase both the pointers to slide the window
                left++;
                right++;
            }
        }

        // here, we finally return the sum
        return ans;
    }
}

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class FirstNegativeInWindowSizeK {

    public static void main(String[] args) {
        int[] arr = {12, -1, -2, 8, -16, 30, 16, 28};
        int k = 3;
        // here in this problem, we have been provided with an array and a window length
        // for each sub-array of size k, we need to find the first negative element that occurred in it
        // answer will be again in form of an array, which will either have the negative element that encountered first in that window
        // or it will be zero representing there was no negative element in that sub-array
        int[] ans = solve(arr, k);

        // print the result
        System.out.println(Arrays.toString(ans));
    }

    private static int[] solve(int[] arr, int k) {
        // given an array of length n, and sliding window size k
        // total sub-arrays possible are n - k + 1
        int[] ans = new int[arr.length - k + 1];

        // we are maintaining a list of negatives (FIFO) structure to hold the negatives that are encountered in the original array
        Queue<Integer> negatives = new LinkedList<>();

        // left and right ptrs to move in the array
        int left = 0, right = 0;

        // ptr to keep track of index in ans
        int ptr = 0;

        // iterate till right is less than overall length
        while (right < arr.length) {

            // find right most element
            int ele = arr[right];
            // if negative add it to the queue
            if (ele < 0) {
                negatives.add(ele);
            }

            // if window size is not reached, increase the window size by moving right ptr
            if (right - left + 1 < k) {
                right++;
            } else if (right - left + 1 == k) {
                // if window size is reached, we need additional logic as demanded in the question
                // if the negatives queue is empty that means no negative element encountered so far
                // so simple add a 0 to the answer/result array
                if (negatives.isEmpty()) {
                    ans[ptr++] = 0;
                } else {
                    // in case the negatives queue is not empty that means we have seen some negative elements in the current sliding window
                    // peek the queue to find the element and store it in answer array
                    ans[ptr++] = negatives.peek();
                    // if the top most element is same as the left most element
                    // then also remove it from the queue
                    if (arr[left] == negatives.peek()) {
                        negatives.remove();
                    }
                }
                // finally increase both left and right pointers
                // to slide the window
                left++;
                right++;
            }
        }
        return ans;
    }
}

public class MaximumOfAllSubArraySizeK {


    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        // here we need to find the max element for each sub-array of given size k
        // so the answer would be 3, 3, 5, 5, 6, 7
        int[] ans = solve(arr, k);
        System.out.println(Arrays.toString(ans));
    }

    private static int[] solve(int[] arr, int k) {

        // maintain left and right to iterate over the window
        int left = 0, right = 0;
        // maintain a result/ans array to store the ans
        int[] ans = new int[arr.length - k + 1];
        // here we take a doubly linked list to build the additional logic as we need to insert and remove from both ends
        Deque<Integer> temp = new LinkedList<>();
        // ptr to maintain the index of elements in ans array
        int ptr = 0;
        // iterate till right is less than array length
        while (right < arr.length) {
            // find the right most element and it has to be appended to the temp list based on logic
            int ele = arr[right];

            // if the temp list is not empty and element on right most side is the largest element
            // then we can simply discard all elements on the left which got added to the deque
            while (!temp.isEmpty() && temp.peekLast() < ele) {
                temp.removeLast();
            }
            // add the right most element to the last
            temp.addLast(ele);

            // if the window size is not reached, increase the right pointer
            if (right - left + 1 < k) {
                right++;
            } else if (right - left + 1 == k) {
                // if the window size is reached, we need additional logic before sliding the window

                // now, we peek the first element from the deque and maintain it in the ans array
                ans[ptr++] = temp.peekFirst();
                // if the first element is same as the left most element of the array which we need to slide,
                // then we remove it from the deque
                if (arr[left] == temp.peekFirst()) {
                    temp.removeFirst();
                }
                // finally slide the window
                left++;
                right++;
            }
        }
        return ans;
    }
}

public class CountOccurrenceOfAnagrams {

    public static void main(String[] args) {
        String str = "aabaabaa";
        String pattern = "aaba";
        // basically in this problem, we need to prepare all the anagrams
        // for given pattern and find in original string
        // the size of window is not given to us,
        // but logically it is same as the size of pattern (because all anagrams of pattern will be same as the length of pattern)
        // finally we need to see all windows/sub-arrays in str of size pattern length to see if it is a possible anagram of given pattern
        // if yes, we need to increase our answer by 1.
        System.out.println(solve(str, pattern, pattern.length()));
    }

    private static int solve(String str, String pattern, int patternLength) {

        Map<Character, Integer> freqMap = new HashMap<>();
        int left = 0, right = 0;
        int ans = 0;
        int count = 0;

        // prepare frequency map by iterating over pattern
        for (Character c : pattern.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }
        // initialize count by size of frequency map to represent number of distinct characters in pattern
        count = freqMap.size();

        // run till right pointer is less than length of the string
        while (right < str.length()) {

            // get the right most char
            char ch = str.charAt(right);

            // see if the char is there in frequency map
            if (freqMap.containsKey(ch)) {
                // decrease the count of frequency by 1
                freqMap.put(ch, freqMap.get(ch) - 1);

                // check if the frequency count of the char became 0, then reduce the count as well by 1
                if (freqMap.get(ch) == 0) {
                    count--;
                }
            }

            // see if the window side is still not reached, then increase the right pointer only
            if (right - left + 1 < patternLength) {
                right++;
            } else if (right - left + 1 == patternLength) { // if window size is same as pattern lenght both ptr will be increased by 1

                // verify at this time if count is 0, means we are able to match the freq of all chars in freq map,
                // increase the answer by 1
                if (count == 0) ans++;
                // now since we need to shrink the window, we need add on logic
                // find the left char of the window
                Character leftChar = str.charAt(left);

                // if the left char is present in the freqMap
                // we are going to increase the frequency for this char by 1 in freq map
                // also if the freq of this char became greater than 0 this time, then we will increase the count variable also by 1
                if (freqMap.containsKey(leftChar)) {
                    freqMap.put(leftChar, freqMap.get(leftChar) + 1);
                    if (freqMap.get(leftChar) > 0) {
                        count++;
                    }
                }

                // finally shift the window by sliding both pointers
                left++;
                right++;
            }
        }

        return ans;
    }
}