Sliding Window Algorithm
In this article, I am going to consolidate all the problems related to Sliding Window Algorithm which I have come across, from beginner level to advanced level. These are some notes which I found from my placement days, I hope they will help in advancing your knowledge from a basic to an advanced level. For an introductory article on this algorithm, you can go through this.
Longest Substring Without Repeating Characters
Problem:
Given a string, find the length of the longest substring without repeating characters.
Example:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Approach:
Use HashSet to store the characters in the current window [i, j). Then we slide the index j to the right. If it is not in the HashSet, we slide j further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index i. If we do this for all i, we get our answer.
Run through:
abcabcbb
i
j
set = [a], ans = max(0, 0-0+1) = 1abcabcbb
ij
set = [a, b], ans = max(1, 1-0+1) = 2abcabcbb
i j
set = [a, b, c], ans = max(2, 2-0+1) = 3abcabcbb
i j
repeating character found at j, so i++ and remove char at i from set
set = [b, c]abcabcbb
i j
set = [b, c, a], ans = max(3, 3-1+1) = 3abcabcbb
i j
repeating character found at j, so i++ and remove char at i from set
set = [c, a]abcabcbb
i j
set = [c, a, b], ans = max(3, 4-2+1) = 3abcabcbb
i j
repeating character found at j, so i++ and remove char at i from set
set = [a, b]abcabcbb
i j
set = [a, b, c], ans = max(3, 5-3+1) = 3abcabcbb
i j
repeating character found at j, so i++ and remove char at i from set
set = [b, c]abcabcbb
ij
repeating character found at j, so i++ and remove char at i from set
set = [c]abcabcbb
ij
set = [c, b], ans = max(3, 6-5+1) = 3abcabcbb
i j
repeating character found at j, so i++ and remove char at i from set
set = [b]abcabcbb
ij
repeating character found at j, so i++ and remove char at i from set
set = []
Code:
Longest Substring with At Most Two Distinct Characters
Problem:
Given a string S, find the length of the longest substring T that contains at most two distinct characters.
Example:
Input: “aabcd”
Output: 3
Explanation: The answer is “aab”, with the length of 3.
Approach:
We use a sliding window that always satisfies the condition where there are always at most two distinct characters in it. When we add a new character that breaks this condition, we move the starting pointer of our string.
Run through:
aabcd
i
j
k = 0 (character 'a')
ans = max(0, 0-0+1) = 1aabcd
ij
k = 1 (characte 'a')
ans = max(1, 1-0+1) = 2aabcd
i j
k = 2 (character 'b')
ans = max(2, 2-0+1) = 3aabcd
i j
more than two distict characters found, i++aabcd
i j
more than two distict characters found, i++aabcd
ij
ans = max(3, 3-2+1) = 3aabcd
i j
more than two distict characters found, i++aabcd
ij
ans = max(3, 4-3+1) = 3
Code:
Longest Substring with At Most K Distinct Characters
Problem:
An extension to the previous problem, but instead of 2 now you need to have k distinct characters in the substring.
Example:
Input: s = “eceba”, k = 2
Output: 3
Explanation: The answer is “ece”, with the length of 3.
Approach:
This is similar to solving the previous problem with at most 2 distinct characters, but the only difference now is that we need to track the number of distinct characters as well, for which we use the help of a map.
Longest Substring with exact K distinct Characters
Problem:
Given an array A of positive integers, find the number of subarrays with exactly K number of distinct characters.
Example:
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Approach 1 (smart work):
If we are aware of how to find subarrays with “at most k different characters”, then we can extend the above algorithm to find the number of subarrays with “exactly k different characters” using the equation:
exactly(K) = atMost(K) — atMost(K-1)`
