Sliding Window Algorithms Explained

Fast and Efficient Problem Solving Algorithm

Sliding Window Algorithm

The sliding window is an efficient algorithmic approach used to solve problems involving contiguous sequences, such as strings and arrays. It utilizes two pointers to create a dynamic window that can expand and contract based on specific conditions.

How It Work

1. Initialization:
   Begin by placing two pointers (commonly called start and end) at the beginning of the data structure you’re analyzing.

2. Expand:
   Move the end pointer to include new elements within the current window. This allows you to explore new data points as needed.

3. Contract:
   When a specific condition is violated, adjust the start pointer to shrink the window. This helps maintain the properties you’re trying to achieve.

4. Calculate Results:
   Continuously update your results based on the current window size and contents. This ensures you’re capturing the necessary data as the window shifts.

Advantages

1. Time Efficiency: Achieves O(n) complexity, outperforming O(n²) solutions.

2. Ease of Use: Simple to grasp and implement, reducing development time.

3. Versatility: Works for a wide range of problems with varying window sizes.

4. Less Redundancy: Avoids repeated calculations, enhancing performance.

5. Logical Flow: Clear structure makes it easy to understand and debug

Important Problems on LeetCode

1. Longest Substring Without Repeating Characters

   leetcode: 3

   public int lengthOfLongestSubstring(String s) {
           HashMap<Character, Integer> charIndexMap = new HashMap<>(); // Store last index of each character
           int maxLength = 0; // Maximum length of substring
           int start = 0; // Starting index of current substring
   
           for (int end = 0; end < s.length(); end++) {
               char currentChar = s.charAt(end); // Current character
   
               // If character was seen before, update start index
               if (charIndexMap.containsKey(currentChar)) {
                   start = Math.max(start, charIndexMap.get(currentChar) + 1);
               }
   
               charIndexMap.put(currentChar, end); // Update the character's last index
               maxLength = Math.max(maxLength, end - start + 1); // Update max length
           }
           return maxLength; // Return the result
   }

2. Subarrays with K Different Integers

   leetcode: 992

   public int subarraysWithKDistinct(int[] nums, int k) {
           int[] frequency = new int[nums.length + 1]; // Frequency array for counting distinct elements
           int startIndex = 0, validSubarrayCount = 0, totalCount = 0; // Initialize pointers and answer variable
   
           for (int endIndex = 0; endIndex < nums.length; endIndex++) {
               // Increase frequency of the current number
               if (frequency[nums[endIndex]]++ == 0) k--; // If new distinct number, reduce k
   
               // While we have more than k distinct numbers
               while (k < 0) {
                   --frequency[nums[startIndex++]]; // Decrease frequency of the start number
                   k++; // Restore k since we removed a distinct number
                   validSubarrayCount = 0; // Reset current count
               }
   
               // If we have exactly k distinct numbers
               if (k == 0) {
                   // Count how many valid subarrays can be formed
                   while (frequency[nums[startIndex]] > 1) {
                       --frequency[nums[startIndex++]]; // Reduce frequency of start number
                       validSubarrayCount++; // Count the valid subarrays
                   }
                   totalCount += validSubarrayCount + 1; // Add the count to the total
               }
           }
           return totalCount; // Return the total number of subarrays
   }

3. Minimum Window Substring

   leetcode: 76

   public String minWindow(String source, String target) {
           // Convert the source string to a character array
           char[] sourceArray = source.toCharArray();
           int[] targetCount = new int[128]; // Frequency array for characters in target
   
           // Count occurrences of each character in target
           for (char ch : target.toCharArray()) {
               targetCount[ch]++;
           }
   
           int requiredChars = target.length(); // Total characters needed
           int leftPointer = 0, rightPointer = 0; // Pointers for the sliding window
           int minLength = Integer.MAX_VALUE; // Minimum length of valid window
           int startIndex = 0; // Starting index of the minimum window
   
           // Iterate until the end of the character array of source
           while (rightPointer < sourceArray.length) {
               // Check if character at right pointer is needed
               if (targetCount[sourceArray[rightPointer]] > 0) {
                   requiredChars--;
               }
               targetCount[sourceArray[rightPointer]]--; // Include current character
               rightPointer++;
   
               // When all required characters are found
               while (requiredChars == 0) {
                   // Update minimum length and starting index if current window is smaller
                   if (rightPointer - leftPointer < minLength) {
                       startIndex = leftPointer;
                       minLength = rightPointer - leftPointer;
                   }
   
                   // Slide the left pointer to the right
                   if (targetCount[sourceArray[leftPointer]] == 0) {
                       requiredChars++; // Need this character again
                   }
                   targetCount[sourceArray[leftPointer]]++; // Remove the left character
                   leftPointer++;
               }
           }
           // Return the minimum window substring or an empty string if not found
           return minLength == Integer.MAX_VALUE ? "" : new String(sourceArray, startIndex, minLength);
       }

4. Find All Anagrams in a String

   leetcode: 438

   public List<Integer> findAnagrams(String s, String p) {
           List<Integer> result = new ArrayList<>();
           int pLength = p.length();
           int sLength = s.length();
   
           if (sLength < pLength) return result;
   
           // Frequency array for characters in p
           int[] pCount = new int[26];
           for (char c : p.toCharArray()) {
               pCount[c - 'a']++;
           }
   
           // Frequency array for the current window in s
           int[] sCount = new int[26];
   
           // Initial window setup
           for (int i = 0; i < pLength; i++) {
               sCount[s.charAt(i) - 'a']++;
           }
   
           // Check if the initial window is an anagram
           if (areCountsEqual(pCount, sCount)) {
               result.add(0);
           }
   
           // Slide the window over s
           for (int i = pLength; i < sLength; i++) {
               // Add the new character to the current window
               sCount[s.charAt(i) - 'a']++;
               // Remove the character that is sliding out of the window
               sCount[s.charAt(i - pLength) - 'a']--;
   
               // Check if the current window is an anagram
               if (areCountsEqual(pCount, sCount)) {
                   result.add(i - pLength + 1);
               }
           }
   
           return result;
   }
   
       // Check if two frequency arrays are equal
       private boolean areCountsEqual(int[] pCount, int[] sCount) {
           for (int i = 0; i < 26; i++) {
               if (pCount[i] != sCount[i]) return false;
           }
           return true;
       }

5. Permutations in String, leetcode: 567

6. Longest Repeating Character Replacement, leetcode: 424

7. Minimum Size Subarray Sum, leetcode: 209

8. Contains Duplicates II, III, leetcode: 220, 219

Conclusion

These problems are great for practicing the sliding window, as they often require efficiently managing a dynamic subset of data. By solving these problems, you’ll enhance your algorithmic skills.

If you found this post helpful, consider subscribing for more updates or following me on LinkedIn, and GitHub. Have questions or suggestions? Feel free to leave a comment or contact us. Happy coding!!