Buttercola: Leetcode: 340. Longest Substring with At Most K Distinct Characters

Buttercola: Leetcode: 340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = "eceba" and k = 2,

T is "ece" which its length is 3.

Understand the problem:
The problem is very similar to the Leetcode question 3 (Longest Substring Without Repeating Characters). 

The key idea of the solution is to use two pointers to maintain a "sliding window". We also use a HashMap to store all the characters in the window. Each time we move forward the "start" pointer and increase the size of the sliding window until the size of the window is greater than K. Then we can easily calculate the size of the window which contains at most K distinct characters. The next step is to shrink the window by moving forward the "end" pointer. In order to get the maximum window size, we must move the minimum steps of the end pointer. So each step we move the end pointer, we need to update the map and remove the character out of the sliding window. The stop condition is that when the window size is again equal to the K, which means the window contains K distinct characters. That's the minimum steps we need to move forward the end pointer. 

The only trick here is we need to check at the last that if the start pointer is out of boundary, we still need to check if the largest window size. That's a common trick for major string w/ two pointer problems.

Read full article from Buttercola: Leetcode: 340. Longest Substring with At Most K Distinct Characters