• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:
Input: s = "aa", k = 1
Output: 2 Explanation: The substring is "aa" with length 2.

Solution:


Prerequisite: Sliding Window

We will go on EXPANDING the window as long as we have at most k distinct characters in the current window. As soon as we get a (k + 1)th character we take note of the length of the current window (which does not include this (k + 1) character), because it may so happen that the current window is the longest substring with at most two distinct characters. Alternatively, we can keep track of the maxLength at every iteration, as we will do in the code below.

Now we prepare for the next window. This is where SHRINKING comes into play. To accommodate for the newly found ((k + 1)th) distinct character we need to get rid of all the instances of the first distinct character from the window. Since we are looking for substring, this would mean the new window would start from the index right after the occurrence of the last index of the first character, because this would enable getting rid of all the instances of the first distinct character leaving only the instances of (k - 1) previously found distinct characters and newly found k-th distinct character in the new window.

It is important to understand what I mean by first distinct character: first distinct character is the character which has the lowest lastIndex. When we find (k + 1)th distinct character, we get rid of this first character.

This means we need to keep track of the last occurrence of every distinct character, and remove them when not needed (i.e, outside of the current window).

As always we will keep track of the beginning and ending of the window with the help of TWO POINTERS.

Java Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave