Member-only story
Longest Substring with At Most K Distinct Characters in C# and Typescript
LeetCode problem link :
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/
Algorithm Used :
This solution makes use of the ‘Sliding Window Algorithm’.
Sliding Window Algorithm :
This algorithm makes use of a contiguous chain of elements which may change in size depending on the needs of the problem. One thing which will remain constant is that the chain will not be broken, it may shorten or elongate based on the need. This structure we usually create using two pointers called ‘start’ and ‘end’. This algorithm is normally used to calculate the max and the min length within the scope of a problem. For certain problem it reduces the time complexity from O(n²) to O(n) because instead of iterating over the collection twice to track the two pointers, we are doing it in a single loop.
Approach :
Our approach starts from declaring two variables namely ‘start’ and ‘end’ which will help us track the start and end of our sliding window. The ask from the problem is to find the longest length of the string which has ‘k’ most distinct character. So from the problem statement we get two…
