Sliding Window Problems: LeetCode
Published: 2023-08-06 08:50:39

****Sliding Window doesn't work when there are negative integers in the array, For example: Finding number of subarrays from an array whose sum is equal to k, the array might contain negative Integers** ([560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/description/))

## Sliding Window Number Related:

[1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold](https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/)

Fixed window size, Slide this fixed window size to achieve a fixed target, problem asked to find how many ways different windows can achieve the target

To solve this problem efficiently, we can use the sliding window approach and avoid recalculating the sum of each sub-array at every step. Instead, we can update the window sum by subtracting the element that goes out of the window and adding the new element that enters the window. This way, we can achieve a time complexity of O(n), where n is the length of the input array.

```
public static int numOfSubarrays(int[] nums, int k, int threshold) {
    int start = 0; // Start index of the sliding window
    int end = 0; // End index of the sliding window
    int resultSubArrays = 0; // Number of sub-arrays with average >= threshold
    int windowSum = 0; // Sum of elements in the current window
    int windowAvg = 0; // Average of elements in the current window

    // Calculate the sum of the first k elements to initialize the window
    while (end < k) {
        windowSum += nums[end++];
    }
    windowAvg = (int) Math.abs((double) windowSum / k); // Calculate the average of the initial window

    // Check if the first window meets the threshold condition and update the result count
    if (windowAvg >= threshold) {
        resultSubArrays++;
    }

    // Continue sliding the window to calculate the sum and average of subsequent sub-arrays
    while (end < nums.length) {
        // Slide the window by removing the leftmost element and adding the rightmost element
        windowSum -= nums[start];
        start++;
        windowSum += nums[end];
        end++;

        // Calculate the average of the current window
        windowAvg = (int) Math.abs((double) windowSum / k);

        // Check if the current window meets the threshold condition and update the result count
        if (windowAvg >= threshold) {
            resultSubArrays++;
        }
    }
    return resultSubArrays;
}
```

## Sliding Window String Related:

3. Longest Substring Without Repeating Characters

*Variable Window Size Problem, Maximize the window size by moving and changing start and end

The solution idea is to use a sliding window approach to traverse the string and maintain a HashMap (windowSubstring) to keep track of the characters in the current window and their last positions in the string. The start and end variables represent the current window's boundaries. The maxResultSize variable holds the length of the longest substring without repeating characters found so far.

```
public int lengthOfLongestSubstring(String s) {
    int start = 0; // start of the current window.
    int end = 0; // end of the current window.
    int maxResultSize = Integer.MIN_VALUE; //store the length of the longest substring found so far.

    HashMap<Character, Integer> windowSubstring = new HashMap<>(); 
//HashMap to store characters in the current window and their last positions.

    while (end < s.length()) {

        Character currentChar = s.charAt(end); // Get the character at the end index.

        while (windowSubstring.containsKey(currentChar)) {
/* If the current character is already in the window, it means we have a repeating character.
 So, we need to shrink the window from the left (start) until the repeating character is no longer in the window.*/

            windowSubstring.remove(s.charAt(start)); 
//before changing the start pointer remove the character from the current window.

            start++; 

// After this loop, the start pointer will be pointing to the position after the last occurrence of the repeating character.
        }

        windowSubstring.put(currentChar, end); 
        maxResultSize = Math.max(maxResultSize, end - start + 1); 
// Update the maxResultSize with the maximum value of itself and the current window size.

        end++; // Increment the end pointer to expand the window to the right and continue to the next character in the string.
    }

    return maxResultSize == Integer.MIN_VALUE ? 0 : maxResultSize; // Return the length of the longest substring without repeating characters found.
}

```
longest substring with k unique characters

*Variable Window Size Problem, Fixed Target Size , Maximize the window size by moving and changing start and end

Solution  Idea
This problem is based on the variable-size sliding window pattern. We have already solved a similar problem Smallest Subarray with a given Sum using this pattern. We will use the same strategy to solve this problem as well.
Consider each substring as a sliding window.
Start with a sliding window of size 1 (windowStart=0, windowEnd=0).
Initialize a HashMap that stores the character count for each character in the current window.
Iterate over the string and insert new characters in the HashMap until we have exactly K distinct characters in the HashMap.
At this point, we have a window (subarray) that conforms to our criteria of having exactly K unique characters. So remember the length of this window as the longest window so far.
However, if the count of distinct characters in the HashMap is greater than K, then we will start shrinking the window from the left until the count becomes smaller than or equal to K. To shrink the window, we will need to discard the leftmost element of the window from the HashMap.
private static int findLengthOfLongestSubstringWithKUniqueCharacters(String s, int k) {
    int n = s.length(); // Length of the input string
    int ansWindowStart = 0; // Starting index of the answer window (substring with k unique characters)
    int ansWindowEnd = 0; // Ending index of the answer window (substring with k unique characters)
    int maxLen = -1; // Stores the length of the longest substring with k unique characters found so far.
    Map<Character, Integer> windowCharCount = new HashMap<>(); // Stores the character count for each character in the current window
    int windowStart = 0; // Starting index of the current window

    // Loop through the input string using a sliding window approach
    for (int windowEnd = 0; windowEnd < n; windowEnd++) {
        // Add the next character to the sliding window
        char c = s.charAt(windowEnd);
        windowCharCount.put(c, windowCharCount.getOrDefault(c, 0) + 1);

        // Shrink the sliding window, until we have exactly 'k' distinct characters in the window
        while (windowCharCount.size() > k) {
            char leftChar = s.charAt(windowStart);

            // Discard the character at windowStart since we're gonna move it out of the window now.
            windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1);
            if (windowCharCount.get(leftChar) == 0) {
                windowCharCount.remove(leftChar);
            }
            windowStart++; // Shrink the window
        }

        // Update maximum length found so far if the current window contains k distinct characters
        if (windowCharCount.size() == k) {
            maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
        }

  // Update the answer window indices if the current window is longer than the previous answer window
        if (windowCharCount.size() == k && windowEnd - windowStart + 1 > maxLen) {
            ansWindowStart = windowStart;
            ansWindowEnd = windowEnd;
            maxLen = windowEnd - windowStart + 1;
        }
    }

    return maxLen; // Return the length of the longest substring with k unique characters.
//(if substring print asked)return maxLen == -1 ? "" : s.substring(ansWindowStart, ansWindowEnd + 1);

}

438. Find All Anagrams in a String

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.


Fixed Target(the character frequencies in target string, fixed number of unique characters), Fixed Window Size (target's character frequency), try to maintain target size and window size equal keeping all the frequencies same in both of the string and target

public List<Integer> findAnagrams(String s, String p) {
    int[] targetMap = new int[26]; // character frequencies in 'p'
    int[] windowCharFreqMap = new int[26]; //character frequencies in the sliding window
    int targetSize = 0; // Number of distinct characters in 'p'
    List<Integer> resultList = new ArrayList<>(); // store the starting indices of anagrams

    // Populate the 'targetMap' with character frequencies from 'p'
    for (char c : p.toCharArray()) {
        targetMap[c - 'a']++;
        targetSize++;
    }

    int start = 0, end = 0, windowSize = 0;

    // Sliding window approach to find anagrams of 'p' in 's'
    while (end < s.length()) {
        char currentChar = s.charAt(end);

 // If the current character is part of 'p', update the sliding window data

        if (targetMap[currentChar - 'a'] > 0) {
            windowCharFreqMap[currentChar - 'a']++;
            windowSize++;

// Shrink the window from the left to maintain the valid anagram size(frequency of each unique characters should be same as the frequency of each unique character in target string), **fixed window size

            while (windowCharFreqMap[currentChar - 'a'] > targetMap[currentChar - 'a']) {
                char startChar = s.charAt(start);
                windowCharFreqMap[startChar - 'a']--;
                windowSize--;
                start++;
            }

//previous while loop responsible for maintaining windows's character's frequency same as the target's character's frequency
//ensuring frequency same, now check if number of unique characters are equal
            if (windowSize == targetSize) {
                resultList.add(start);
            }
        } else {
/*if any character encountered which is not part of the target then ignore that character and start the window from next position of the prvious window*/ 
// If the current character is not part of 'p', reset the window and move to the next index
            Arrays.fill(windowCharFreqMap, 0); // Reset the frequency map for the sliding window
            windowSize = 0; // Reset the size of the sliding window
            start = end + 1; // Move the starting index of new window, to the next position
        }

        end++; // Move the ending index of the sliding window to the right
    }

    return resultList;
}