Sliding Window

311

Longest Substring with K distinct characters
(distinct characters of K size, repeating characters)

int windowStart = 0, maxLength = 0;
Map<Character, Integer> charFrequencyMap = new HashMap<>();

// in the following loop we'll try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
	char rightChar = str.charAt(windowEnd);
	charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
	
	// shrink the sliding window, until we are left with 'k' distinct characters in the frequency map
	while (charFrequencyMap.size() > k) {
		char leftChar = str.charAt(windowStart);
		charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
		if (charFrequencyMap.get(leftChar) == 0) {
			charFrequencyMap.remove(leftChar);
		}
		windowStart++; // shrink the window
	}
	maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}

Fruits into Baskets
(Longest Substring with at most 2 distinct characters)
(distinct characters of K=2 size, repeating characters)

For this problem, we follow the exact same pattern as the previous one, and replace k with 2, to denote 2 baskets. If we think about finding most number of fruits into 2 baskets, it can be translated as find the most number of contingous letters (longest substring) that can be of 2 distinct fruits or characters ( K distinct characters, where K = 2).

int windowStart = 0, maxLength = 0;
Map<Character, Integer> charFrequencyMap = new HashMap<>();

// in the following loop we'll try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
	char rightChar = str.charAt(windowEnd);
	charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
	
	// shrink the sliding window, until we are left with 'k' distinct characters in the frequency map
	while (charFrequencyMap.size() > 2) {
		char leftChar = str.charAt(windowStart);
		charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
		if (charFrequencyMap.get(leftChar) == 0) {
			charFrequencyMap.remove(leftChar);
		}
		windowStart++; // shrink the window
	}
	maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}

Longest Substring with no repeating characters
(distinct characters of ANY size, NO repeating characters)

This is a slight modification of above problem. Previous patterns needed us to look for any frequency of distinct characters (aabbbc is OK) etc, this pattern requires us to look for single instance of all distinct characters (abc only not aabbbc). Therefore, it's of no use for us to store the frequency of the characters, rather we can store the last occurrence/index of the character to know where to pick back up.

If the right character already exists in hashmap (it's a duplicate):

find the prevIndex where this character occurred, map.get(right)
update start to prevIndex+1
in some cases start might be ahead of this value, in that case ignore prev occurrence as it is not in the current sliding window: start = Math.max(start, prevIndex+1);

int windowStart = 0, maxLength = 0;
//store an indexMap, not a frequencyMap as we need only distinct values, not repeating 
Map<Character, Integer> indexMap = new HashMap<>();

for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
	char rightChar = str.charAt(windowEnd);
	if(indexMap.containsKey(rightChar)){
		//check if this rightChar occurs within current sliding window
		//if it does, update start to that prevIndex+1
		int prevIndex = indexMap.get(rightChar);
		windowStart = Math.max(windowStart, prevIndex+1);
	}
	//add current index to map
	indexMap.put(rightChar, windowEnd);
	maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}

Longest Substring of the same character
(distinct character of size K=1 where char = X, repeating characters)

Longest Substring of the same character, with replacement of K characters

Longest Subarray of 1s, with replacement of K digits

Comments (0)