Sliding Window Technique and Question Bank

Prashant Nigam

55166

Sliding Window Career

Overview

Sliding Window Technique is a popular method in algorithmic problems because of its high efficiency (mostly linear)
It helps to avoid computing repetitive problems by computing only the new part that's introduced in the data set and discarding the one that moves out, usually 1 at a time.
There are 2 categories of SWT problems:
- Fixed sized window: The window remains of a consant size (say k), which slides/moves along a data structure. Imagine sliding window panel along a long ridge
- Variable sized window: The window fluctuates in size, but still slides/moves along a data structure. Imagine a spring compressing and expanding while moving along a plane
There are plenty of articles explaining the what and how, so this post isn't gonna repeat on that. This post is to sketch out a rough algorithm which can be tweaked for most problems on SW
This is meant to be a continuosly improving post and I'll keep updating it and add more problems as I progress.
Collaboration works wonders so I'd encourage anyone reading this post to feel free to contribute for the benefit of the community.

Sample Problem: Longest Substring Without Repeating Characters.

Given a string s, find the length of the longest substring without repeating characters.

Algorithm

Use a hashMap to keep track of the latest index of each letter
Keeping the left pointer at rest, move the right pointer by 1 letter at a time.
When a repeating character is encountered, update the maxLength and move the left pointer to max{left pointer, old last occurence of this character as available in the map}. We do a max because we don't want to take the left pointer backwards at any time (e.g. in "abba"), it will only move forward or stay still.
return max {right-left, maxLength}. Doing this outside the loop is essential as it handles strings with all unique chars.

T/S: O(n)/O(a), where n = s.length, a = size of character set

public int lengthOfLongestSubstring(String s) {
	var n = s.length();
	
	if (n < 2)
		return n;
		
	var left = 0;
	var right = 0;
	var maxLength = 0;
	var map = new HashMap<Character, Integer>(); // map of char to its latest index

	while (right < n) {
		var ch = s.charAt(right);
		
		if (map.containsKey(ch)) {
			maxLength = Math.max(maxLength, right - left); // record max window size
			left = Math.max(left, map.get(ch) + 1); // shrink window from left
		}
		
		map.put(ch, right); 
		right++ // expand window to the right
	}
	
	return Math.max(maxLength, right - left);
}

Question Bank

A slight variation using the template for Sliding Window that can be used in the following problems that follow a similar pattern:

Sliding Window Technique and Question Bank

Overview

Algorithm

Question Bank

Fix Sized Window

Variable Sized Window