# Sliding Window Algorithm explained

- Longest Substring Without Repeating Characters
- Longest Substring with At Most Two Distinct Characters
- Longest Substring with At Most K Distinct Characters
- Longest Substring with exact K distinct Characters

## 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.

1 | abcabcbb |

1 | public int lengthOfLongestSubString(String s) { |

## 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.

1 | aabcd |

1 | public int lengthOfLongestSubStringTwoDistinct(String s) { |

## 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.

1 | public int lengthOfLongestSubStringKDistinct(String s) { |

## 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)`

1 | public int lengthOfLongestSubStringAtMostKDistinct(String s, int k) { |