Longest Substring with At Most K Distinct Characters

Longest Substring with At Most Two Distinct Characters is a generalized form of the problem of finding the longest substring with at most two distinct characters. They both can be solved using the sliding window technique.

This problem is a combination of elements seen in problems like “Longest Substring Without Repeating Characters” (LeetCode 3) and “Minimum Size Subarray Sum” (LeetCode 209). Here’s how:

“Longest Substring Without Repeating Characters” (LeetCode 3): This problem asks for the longest substring without any repeating characters. This is similar to our problem, which also requires a longest substring. However, our problem allows for K unique characters, not just one. Therefore, our problem is a generalization of LeetCode 3. The sliding window concept used in LeetCode 3 is also used here, where we move a window through the string to find the longest possible valid substring.
“Minimum Size Subarray Sum” (LeetCode 209): This problem asks for the minimum length of a continuous subarray whose sum is equal to or greater than a given target. This relates to our problem because we also have a target limit (the number of unique characters, K), and we also want to find a subarray (or in this case, a substring) that meets that requirement. In our case, instead of summing the elements, we are counting the number of unique characters. So, the approach in our problem is similar to LeetCode 209 in that we have to adjust the window size based on a certain condition.

Combining these elements – finding the longest substring (from LeetCode 3) and adjusting our window based on a condition (from LeetCode 209) – gives us our approach to solve this problem.

10 Prerequisite LeetCode Problems

This is a typical sliding window problem where you need to keep track of the frequency of characters in the current window and update the window accordingly. Here are 10 problems of lesser complexity to build up to it:

These problems will provide a good understanding of the sliding window technique and how to manage and update the window based on different conditions.

Next Problems

The order in which you tackle these problems depends on your familiarity and comfort with the concepts involved. However, considering the complexity and the elements involved in each problem, I would suggest the following order:

Longest Substring with At Most K Distinct Characters: This problem can serve as a good starting point as it introduces the concept of tracking the count of distinct elements (characters in this case) within a sliding window.
992. Subarrays with K Different Integers: After understanding the basic concept from the previous problem, this problem can add a layer of complexity. Instead of finding the longest range, this problem focuses on counting the number of valid subarrays, providing more practice on handling the sliding window technique.
1248. Count Number of Nice Subarrays: This problem adds another layer of complexity by limiting the counted elements to only odd numbers. This requires an additional check within the sliding window process and would be a good next step after you’re comfortable with the previous two problems.

992. Subarrays with K Different Integers: This problem asks for the number of subarrays with exactly K different integers. While this problem and our current problem both involve dealing with a specific count of unique or distinct elements, they do have a couple of major differences. First, the 992 problem is about subarrays and deals with integers, while our current problem is about substrings and deals with characters. Second, the 992 problem is about finding all subarrays with exactly K unique integers, while our problem is about finding the longest substring with at most K distinct characters. Despite these differences, the underlying approach of using a sliding window to capture a range with a certain number of distinct elements applies to both problems.

1248. Count Number of Nice Subarrays: This problem asks for the number of “nice” subarrays (subarrays with a specific number of odd numbers). There’s a clear similarity here: both problems involve counting a specific type of element within a range (odd numbers in the 1248 problem, distinct characters in our current problem). However, there are also differences. The 1248 problem asks for the total number of such subarrays, while our current problem wants the longest such substring. Additionally, the 1248 problem only considers odd numbers as contributing to uniqueness, while our problem considers all characters. Yet, both problems can leverage the sliding window approach to count the desired elements in each range/subarray/substring.

So, while the specifics of these problems differ, they are similar to our current problem in the way that they use a sliding window approach to deal with unique or specific types of elements within a range.

Problem Analysis and Key Insights

For the problem at hand, which is about finding the longest substring that contains at most ‘k’ distinct characters, here are some key insights we can extract from the problem statement:

Distinct Characters: The problem mentions the term “distinct characters”. This indicates that we are dealing with a problem related to character frequency/count within substrings. Hence, a common data structure that could come in handy would be a hash map/dictionary, which can efficiently keep track of the frequency of characters.
Longest Substring: The task is to find the longest substring that satisfies a certain condition (at most ‘k’ distinct characters). This hints at a possible application of the sliding window technique. The sliding window approach is often used in problems involving substrings or contiguous array sequences. In this case, the window would represent a substring of the input string.
At most ‘k’: The problem requires that the longest substring must contain “at most ‘k’” distinct characters, not exactly ‘k’ distinct characters. This means that substrings with fewer than ‘k’ distinct characters are also valid. This is important for edge cases where ‘k’ is greater than the total number of distinct characters in the string.
Length of the Substring: The problem asks for the length of the substring, not the substring itself. This allows for potential optimization as we don’t need to keep track of the actual substring, but just the length.

Understanding these key insights will guide us in designing an efficient algorithm for the problem.

Problem Boundary

The scope of this problem involves understanding and manipulating strings and their substrings. You need to be able to:

Iterate over the given string and its substrings.
Keep track of distinct characters within each substring.
Use the sliding window technique to limit the substring’s characters to at most ‘k’.
Calculate the length of these substrings.
Determine the longest valid substring among them.

The problem does not involve changing the input string or any of its substrings. The original string order is maintained. The problem is also strictly about string manipulation and does not involve any external data structures other than what might be needed to solve the problem (like using a set or map to keep track of distinct characters).

The constraints also indicate that the problem requires a solution that can handle fairly large strings (up to 50,000 characters) and various values of ‘k’ (up to 50), implying that the solution should be efficient in terms of time complexity.

Establishing the boundary of a problem involves determining its constraints and limitations, as well as the specific input and output types it operates with. Here’s how you can do this for the given problem:

Input constraints: The input will be a string s and an integer k. The length of the string s is within the range [1, 5 * 10^4], and k is in the range [0, 50].
Output constraints: The output should be a single integer, representing the length of the longest substring of s that contains at most k distinct characters.
Operation constraints:
- The string s will contain lowercase English letters only.
- The substring should be continuous.
- The substring can contain at most k distinct characters.
- If k is 0, the output should be 0 as well because we cannot have any characters in the substring.
Efficiency: Given the potential size of the input string, the solution should ideally have a linear time complexity (O(n)).

By taking these constraints into account, we’ve established the boundaries of the problem. Any solution we create will need to operate within these boundaries.

Problem Classification

The problem falls into the domain of “Strings & Arrays” in Data Structures and Algorithms. The problem specifically deals with the properties and manipulations of substrings within a string, which is a commonly encountered topic in this domain.

“What” Components:

String: The problem provides an input string ’s’ and we are asked to identify certain properties about its substrings. String manipulation is a key part of the problem.
Integer ‘k’: An integer ‘k’ is provided which determines the maximum number of unique characters a valid substring can contain.
Substrings: The problem revolves around identifying specific substrings in the given string ’s’. A substring is a contiguous sequence of characters within a string.
Distinct Characters: The concept of ‘distinct characters’ is important in this problem. We are asked to find substrings that have ‘at most k’ distinct characters.
Length of Substring: The output of the problem is the length of the longest valid substring, not the substring itself. Hence, length calculation of substrings is a vital component of this problem.

This can be classified as a “Sliding Window” problem. The sliding window technique is commonly applied to problems where we are asked to find or calculate something about all contiguous substrings (or subarrays) that satisfy a particular condition. In this case, the condition is that the substring should have ‘at most k’ distinct characters, and we need to find the maximum length among such substrings.

Distilling the Problem to Its Core Elements

Fundamental Concept or Principle: The problem is based on the concept of “sliding window” in string/array manipulation. This concept is often used when we want to keep track of a subset of data that falls within a certain range in an array/string, and the problem requires us to track the maximum or minimum length of such a subset (in this case, a substring).

Simplest Description: We have a string of letters and a number. We need to find the longest continuous part of the string that includes at most the given number of unique letters.

Core Problem: The core problem we are trying to solve is to find the longest substring that contains at most k distinct characters.

Simplified Problem Statement: What is the length of the longest continuous section of a given string that includes no more than a certain number of different letters?

Key Components:

String manipulation: We need to work with substrings in the given string.
Counting distinct characters: We need to track the number of distinct characters in a substring.
Sliding window: We need to adjust our window (i.e., substring) as we traverse through the string to find the longest valid substring.

Minimal Set of Operations:

Initialize a window on the string.
Count the distinct characters in the window. If it exceeds k, move the window.
At each position, calculate the length of the current window. Keep track of the maximum length.
Continue this process until the entire string has been traversed. Return the maximum length tracked.

Visual Model of the Problem

This is a classic sliding window problem. The idea is that we use two pointers to create a window of characters in the string. We expand the window as long as there are no more than k distinct characters in it. When there are more than k distinct characters, we shrink the window from the left until there are at most k distinct characters again.

Here’s a visualization of how it works using the first example:

Consider the string s = "eceba" and k = 2:

Initially, we start with an empty window:
[_____]
We add the first character, e, to the window:
[e____]
We add the second character, c, to the window. Now we have two distinct characters, which is still not more than k:
[ec___]
We add the third character, e, to the window. We still have two distinct characters:
[ece__]
We add the fourth character, b, to the window. Now we have three distinct characters, which is more than k. So, we shrink the window from the left until there are at most k distinct characters:
[ceb__]
We add the last character, a, to the window. Again, we have three distinct characters, so we shrink the window from the left:
[eba__]
We’ve reached the end of the string, so we stop. The longest substring with at most k distinct characters was ece, which has length 3.

This problem can be solved efficiently by keeping track of the frequency of each character in the window and the number of distinct characters. When the number of distinct characters exceeds k, we can decrement the frequency of the character at the left end of the window and remove it from the count of distinct characters if its frequency becomes 0. We keep track of the maximum length of the window we’ve seen so far, which will be our answer.

Problem Restatement

We are given a string and a number. The string can have any length, and it’s made up of characters. The task is to figure out the longest part of the string (which we’ll call a substring) that includes no more than the given number of different characters. We should return the length of this longest substring.

To clarify:

The substring can start and end at any point within the string, but the characters must be consecutive (i.e., no skipping characters).
The number given, let’s call it “k”, is the maximum number of unique characters that the substring can contain. If a substring contains more than k unique characters, it is not considered valid.
We are only interested in the length of the longest valid substring, not the substring itself.

In terms of constraints:

The length of the string is at least 1 and at most 50,000.
The value of “k” (the maximum number of unique characters allowed in the substring) is at least 0 and at most 50. If “k” is 0, it means the longest valid substring can only be of length 0 since it can’t contain any characters.

Abstract Representation of the Problem

Let’s formulate an abstract representation:

Let’s consider the string as a sequence “S” of length “n” composed of elements (characters) from a finite set. The sequence S has an order, meaning that each element in the sequence has a specific position.

We are given an integer “k” which is a limit. The goal is to find the longest subsequence “Sub” from the sequence “S” such that the subsequence maintains the order of elements (i.e., it is a continuous slice of the sequence), and has at most “k” distinct elements.

The output of the problem is the length of the longest such subsequence “Sub”.

By translating the problem into this abstract representation, we shift our focus from the specific details (like strings and characters) to the underlying structure of the problem, which involves sequences, subsequences, and the concept of distinct elements. This abstract view might help us think about similar problems in other contexts or identify applicable algorithms or techniques from computer science theory.

Terminology

There are a few terms and concepts that are essential to understand this problem:

String: A string is a sequence of characters. In computer science, a string is typically used to represent text. In this problem, we are given a string, and we need to find a substring within it.
Substring: A substring is a contiguous sequence of characters within a string. In this problem, we are looking for a specific kind of substring - one that contains at most ‘k’ distinct characters.
Distinct Characters: When we say ‘k distinct characters’, we mean ‘k different characters’. For instance, in the string “aaabc”, there are 3 distinct characters - ‘a’, ‘b’, and ‘c’.
Length of a string/substring: The length of a string (or substring) is the number of characters it contains. We want to maximize this quantity for the substring that we find.
Sliding Window: While it’s not explicitly mentioned in the problem statement, the concept of a “sliding window” is often used to solve problems like this. A “window” in a string is a substring. The window is “sliding” because we move it along the string, one character at a time, adjusting its start and end points as we go.
Hashing/Hash Map: A hash map, or a dictionary, allows us to store and retrieve values in constant time (on average). It’s a key-value storage where each value is associated with a unique key. In this problem, a hash map can be used to store the count of each character in the current window.

In this problem, we’ll likely use a sliding window approach and a hash map to keep track of the count of each character in the current window. As we slide the window along the string, we update the hash map and check the number of distinct characters in the window.

Problem Simplification and Explanation

Let’s break down this problem into simpler terms:

The problem is asking us to look at a series of characters (a string) and find the longest sequence (substring) within it that has at most a certain number (k) of unique characters.

A good way to think about this might be to imagine you’re given a long chain of differently colored beads, and you’re asked to find the longest stretch of chain where there are no more than ‘k’ unique colors.

If k equals to 2, for example, you’d be looking for the longest part of the chain where there are 2 or fewer unique bead colors. It doesn’t matter if the same color appears multiple times. It’s still considered as one unique color.

The key concepts involved are:

String/Character sequence: This is the chain of beads. Each character is like a bead on the chain.
Substring: This is a section of the chain. In the problem, we’re trying to find the longest section (substring) that meets certain criteria.
Distinct Characters: These are the unique colors of the beads. We want to find the longest section of the chain that contains at most ‘k’ unique colors.
Length of a substring: This is the number of beads in a section of the chain. We want to find the section that is as long as possible.

To solve the problem, we’d typically use a method called the ‘sliding window’ approach. This is like taking a magnifying glass and moving it along the chain, looking at a small section at a time. As you move the magnifying glass (the ‘window’), you keep track of the number of unique colors (distinct characters) you see. Whenever the number of unique colors exceeds ‘k’, you move the start of the magnifying glass further along the chain. You continue this process until you’ve looked at every part of the chain, and the longest section you’ve found that meets the criteria is your answer.

Constraints

Let’s examine the problem statement and the constraints to identify specific characteristics that can be exploited for an efficient solution:

String length (s.length): The problem constraints specify that the length of the string is within the range [1, 5 * 10^4]. This gives us an upper limit on the number of characters we need to process.
The value of ‘k’ (distinct characters): This is another important constraint in the problem. It can range from 0 to 50. Since ‘k’ is the maximum number of distinct characters we’re allowed in a substring, and it’s relatively small, we can use this to our advantage. This constraint allows us to use a hash map or similar data structure to track the unique characters and their counts in our current substring (or sliding window). We can then easily check if we have exceeded ‘k’ distinct characters by checking the size of our hash map.
Distinct characters in the string: Since the problem is dealing with strings, we’re working within a limited character set (e.g., ASCII, Unicode, etc.). For ASCII, for example, we have 128 possible characters, which could be another point to exploit depending on the input and programming language being used.
Substring structure: The problem asks for the longest substring with at most ‘k’ distinct characters. This suggests using a sliding window strategy, where we continually adjust our current substring to find the longest satisfying the condition.
String order: The problem statement does not require us to preserve the order of characters in our result, just to find the longest substring with at most ‘k’ distinct characters. However, the need to maintain character order within the substring guides our approach to a sequential, sliding window method.
Non-negative ‘k’: The fact that ‘k’ can be 0 adds a specific condition to handle. When ‘k’ is 0, we should return 0 since no distinct characters are allowed in the substring.

Understanding these characteristics allows us to tailor a solution that fits within these boundaries and conditions. This could mean using specific data structures (like a hash map for tracking character counts), and employing certain strategies (like the sliding window technique), which play to these constraints for an efficient solution.

From the constraints, we can identify several key insights that can help us develop an efficient algorithm:

Limited number of distinct characters: The constraint that k (the maximum number of distinct characters allowed in a substring) is less than or equal to 50 is a significant factor. This insight suggests that a solution approach can effectively leverage data structures like a hash map to keep track of the distinct characters within a substring without worrying about excessive space complexity.
Manageable string length: The maximum length of the input string is 5 * 10^4. While this is a large number, it’s not so large that it rules out solutions with a time complexity of O(n) or O(n log n). This suggests that we can solve the problem using iterative methods and data structures with linear or near-linear time complexities.
Substrings and sliding window: The problem deals with substrings within a larger string and requires us to find the longest such substring under a certain condition (at most k distinct characters). This kind of problem often lends itself well to a “sliding window” approach, where we maintain a “window” into the string that we can move and resize to check different substrings.
Non-negative ‘k’: Since ‘k’ can be 0, our algorithm must correctly handle this case. It gives the insight that when ‘k’ is 0, no characters can form a substring, so the result is 0.

By understanding these insights, we can start to form a picture of the problem-solving strategy. It involves iterating over the string, using a data structure to keep track of distinct characters and their counts, and applying a sliding window approach to identify the longest qualifying substring.

Case Analysis

Let’s categorize and consider a range of input cases to cover a wide spectrum of the problem. Here are some edge cases, typical cases, and special cases:

Edge Case - Empty String (Minimum Length Case)
Here, the input string ’s’ is an empty string, and ‘k’ can be any number from 0 to 50.
Example: s = “”, k = 2
In this case, since there are no characters in the string, there is no substring, so the longest substring with at most ‘k’ distinct characters is also an empty string, and the output is 0.
Edge Case - String with Single Character
In this case, the string ’s’ consists of a single repeated character, and ‘k’ is 1.
Example: s = “aaaaa”, k = 1
Here, the entire string is a valid substring as there’s only one distinct character, so the output is the length of the string, which is 5 in this example.
Edge Case - ‘k’ is Zero
For this case, ‘k’ is zero, and ’s’ can be any string.
Example: s = “abac”, k = 0
Since ‘k’ is zero, no characters can form a substring. So, the output is 0, irrespective of what string is provided.
Typical Case - String with Multiple Characters and ‘k’ > 1
Here, the string ’s’ consists of multiple characters, and ‘k’ is greater than 1.
Example: s = “aaabcdeee”, k = 2
For this example, the longest substring with at most 2 distinct characters is “aaab”, so the output is 4.
Special Case - ‘k’ Greater than Number of Distinct Characters in ’s’
In this case, ‘k’ is greater than the number of distinct characters in ’s’.
Example: s = “abc”, k = 5
In this case, the longest substring is the entire string itself because the entire string has fewer distinct characters than ‘k’. So, the output is the length of ’s’, which is 3 for this example.

By considering these different cases, we can ensure that our solution handles various scenarios and adheres to the constraints of the problem. It’s particularly important to handle edge cases correctly to avoid errors and ensure the robustness of the solution.

From analyzing the different cases, we can derive several key insights:

Empty String or Zero ‘k’: If the string is empty or ‘k’ is zero, the length of the longest substring with at most ‘k’ distinct characters will be 0. This is because we either have no characters to form a substring, or we can’t include any distinct characters in the substring.
Single Character Strings or ‘k’ >= Number of Distinct Characters: In cases where the string is made up of only one character or ‘k’ is greater than or equal to the number of distinct characters in the string, the length of the longest substring will be equal to the length of the input string. This is because all characters in the string can be included in the substring without exceeding the distinct character limit.
‘k’ Distinct Characters: For cases with more than ‘k’ distinct characters, we need to find the longest continuous segment of the string that contains at most ‘k’ distinct characters.
Multiple Characters with ‘k’ > 1: When we have multiple characters and ‘k’ is greater than 1, we will have to iterate through the string and keep track of the distinct characters and their counts to determine the longest substring that fits the criteria.

These insights can guide our approach to solving the problem, and can help us formulate a solution strategy. In this problem, it seems that a sliding window approach would be particularly useful to track the longest substring with at most ‘k’ distinct characters as we iterate through the string.

Identification of Applicable Theoretical Concepts

This problem can be effectively solved by employing a sliding window technique, which is a popular approach for dealing with string and array problems in computer science.

Here’s a rough outline of how it would work:

Sliding Window: This technique maintains a ‘window’ of elements in the string. The window is typically defined by two indices, ‘start’ and ’end’, and slides through the string to cover different substrings.
HashMaps or Counters: To count the distinct characters in the current window, we can use a HashMap or a Counter data structure. This way, we can have constant time access to check if a character is in the window and to get its count.
Two Pointers: With the sliding window technique, we often use two pointers. One (let’s call it ‘right’) goes through each element from left to right. Another (let’s call it ’left’) adjusts the window size. If the window does not meet the requirement (in this case, having more than ‘k’ distinct characters), we move the ’left’ pointer one step to the right to decrease the window size.
Max Length Tracking: To get the length of the longest substring that contains at most ‘k’ distinct characters, we can keep track of the maximum length of valid substrings as we move our window.

This problem does not directly involve complex mathematical concepts. However, understanding the properties of string manipulation, the nature of substrings, and the concept of character uniqueness are important for devising an efficient solution.

Simple Explanation

Let’s think about it as a fun word game.

Imagine you have a long word, and your task is to find the longest part of this word that contains a certain number of different letters. Let’s say we’re only allowed to use 2 different letters.

For example, if your word is “banana” and you’re allowed to use 2 different letters, the longest part of the word you can make is “nana”, which uses the letters ’n’ and ‘a’.

So, the game is all about finding the longest part of the word that meets the rules of only using a certain number of different letters.

In the context of programming, the word is a “string” of characters, and the different letters are “distinct characters”. The longest part of the word is known as the “longest substring”, and the rule of only using a certain number of different letters is the “constraint”.

Problem Breakdown and Solution Methodology

Here is a detailed step-by-step guide on how you could approach this problem:

Initial considerations: To solve this problem, we need to find a balance between the desire to extend the substring as much as possible and the need to keep the number of distinct characters within the limit. The optimal approach would be to use a sliding window mechanism, where the ‘window’ is the substring we’re currently examining.
Create a sliding window: You start at the beginning of the string and keep adding characters to your window (substring) until you reach a point where adding one more character will exceed the limit of distinct characters (k). For this, you would need a way to keep track of the frequency of each character in your current window, which could be a map or a dictionary data structure.
Slide the window: Once your window exceeds the distinct character limit, you’ll start removing characters from the beginning of the window until you’re back within the limit. Then, you can start adding new characters to the window again.
Keep track of the maximum length: At each step, you’ll check if your current window’s length is longer than the maximum found so far. If it is, you’ll update your maximum.
Iterate until the end of the string: You’ll keep expanding and shrinking your window as needed until you reach the end of the string. At this point, the longest length you’ve recorded will be the answer.

Let’s use an analogy of a moving van to illustrate this. Imagine you’re moving houses and have a van where you can only fit a certain number of unique items (k). As you move along your house (the string), you keep adding items (characters) to the van (your window). When you can’t fit any more unique items, you start unloading the van from the front, until you can fit new items again. All along, you keep track of the maximum number of items you managed to fit in the van, and that’s your answer!

Now, consider an example. Given s = “eceba” and k = 2.

First, you add ’e’ to your window. The window is “e”, the maximum length is 1.
Then, you add ‘c’. The window is “ec”, the maximum length is 2.
Then, you add the second ’e’. The window is “ece”, the maximum length is still 2.
You want to add ‘b’, but that would make 3 distinct characters in the window, exceeding the limit. So you remove ’e’ from the front of the window, and add ‘b’. The window is “ceb”, the maximum length is still 2.
Lastly, you want to add ‘a’, but again it would exceed the limit. So you remove ‘c’ and ’e’ from the front of the window, and add ‘a’. The window is “ba”, the maximum length is still 2.

So, the longest substring that contains at most 2 distinct characters is of length 2.

Inference of Problem-Solving Approach from the Problem Statement

Here are some key terms and concepts, and how they inform the problem-solving approach:

String: This problem is about strings, which are ordered sequences of characters. This hints that we will have to process the characters in a certain order, either from the beginning to the end or vice versa.
Substring: This is a contiguous sequence of characters within a string. The mention of substring often hints at techniques related to string traversal, such as sliding window, which we use in this problem.
Longest: This word indicates that we are looking for a maximum length, which usually involves keeping track of the maximum value found so far during traversal.
At most k distinct characters: This phrase puts a constraint on what counts as a valid substring. We need to count the number of distinct characters in each substring, which calls for a data structure that can track character frequencies, such as a dictionary or a map.
Length: We are interested in the lengths of substrings, not their content. So we only need to track the number of characters in each substring, rather than the substrings themselves.
Return: The problem asks for a single numeric answer, not a substring or a sequence of operations. This means we can simplify our task to updating and returning a single variable.

Identifying these key concepts helps us recognize that this problem can be solved by a sliding window approach, where we move a ‘window’ through the string, keep track of character frequencies, and update the maximum length as needed.

The sliding window technique is a common method for solving array or string problems where the task is to find a contiguous subarray or substring that meets certain conditions. In this problem, we are asked to find a longest substring that contains at most ‘k’ distinct characters.

There are a few clues that suggest the sliding window technique would be applicable:

Substrings: The problem deals with finding certain substrings within a given string, which often points towards using a sliding window approach. Substrings are contiguous by nature, which is exactly what a ‘window’ over the input string would represent.
Longest/Shortest or Maximum/Minimum: Whenever we need to find a longest or shortest subarray or substring that satisfies certain conditions, a sliding window approach should be considered. Here we are asked to find the longest substring with at most ‘k’ distinct characters.
“At most K”: The condition to find a substring with ‘at most k distinct characters’ suggests a limit on the window size in terms of distinct characters. The window will ‘slide’ to find the area of the string that satisfies this condition.
Distinct Characters: Keeping track of the number of distinct characters within a window is a condition that can be managed quite well with a sliding window approach, using a dictionary or hash map.

All of these factors combined suggest that the sliding window technique could be a good fit to solve this problem.

Simple Explanation of the Proof

Let’s break down the algorithm for the problem and understand how it works:

The problem statement asks us to find the longest substring with at most k distinct characters.

We are going to use the ‘sliding window’ technique to solve this problem. The term ‘window’ refers to the range of elements in the string that are currently being considered. The ‘sliding’ refers to moving this window over the input string.

Here’s a step-by-step explanation of the algorithm:

Initialize variables: We start by initializing a few variables.
- We have two pointers, left and right, initially both at the start of the string. These will represent the boundaries of our sliding window.
- We also initialize a dictionary (or hashmap) to keep count of the number of times each character appears in our current window.
- Finally, we have a variable to keep track of the maximum length of a valid substring we’ve found.
Expand window: As the first step in our loop, we expand the window to the right by moving the right pointer one step at a time. Each time we move the pointer, we add the new character to our dictionary and update its count.
Validate window: After expanding the window, we check if the number of distinct characters in our window (which is the size of our dictionary) is greater than k. If it is, it means our current window is not a valid substring, as it contains too many distinct characters.
Shrink window: If the window is not valid, we shrink it from the left by moving the left pointer to the right, removing characters from the dictionary as necessary, until the window is valid again, i.e., it contains at most k distinct characters.
Update maximum length: After each round of expanding and potentially shrinking the window, we update our maximum length variable if the length of the current window (i.e., right - left) is greater than the maximum found so far.

This process continues until the right pointer has scanned the entire string. At the end, the maximum length variable will hold the length of the longest substring with at most k distinct characters.

This algorithm works because it essentially examines all possible substrings of the string that contain at most k distinct characters, and keeps track of the longest such substring it has found. The ‘sliding window’ approach allows us to do this efficiently, because when we move the window one step to the right, we can update the character counts in constant time and check if the window is valid without having to recount the number of distinct characters from scratch.

Stepwise Refinement:
Step 1: Initial Setup:
Initialize four variables:
- left (start of the sliding window, set to 0)
- right (end of the sliding window, set to 0)
- max_length (to keep track of the maximum length of substring with at most k distinct characters, set to 0)
- char_count (a dictionary to store the count of characters in the current window, initially empty)
Step 2: Main Loop:
Loop through the string by moving the right pointer. For each character:
- Increment its count in the char_count dictionary.
- While the number of keys in char_count (i.e., the number of distinct characters in the current window) is greater than k, move the left pointer to the right and decrement the count of the character at the left pointer in char_count. If the count becomes 0, remove the character from char_count.
- Update max_length to be the maximum of max_length and the current window length (which is right - left + 1).
Step 3: Result:
After the loop finishes, max_length will be the length of the longest substring with at most k distinct characters.
Distilling into Granular, Actionable Steps:
- Create and initialize the variables left, right, max_length, and char_count.
- Start a loop that continues as long as right is less than the length of the string.
- In each iteration, add the character at right to char_count and increment right.
- If char_count has more than k keys, enter a loop that continues until char_count has k or fewer keys. In each iteration of this loop, decrement the count of the character at left in char_count, and if the count becomes 0, remove the character from char_count. Then increment left.
- After the inner loop (if any), update max_length with the maximum of max_length and right - left.
- After the main loop, return max_length.
Independent Subproblems:
Identifying the characters in the string and counting their occurrences within the sliding window are subproblems that can be solved independently of the rest.
Repeatable Patterns:
- The sliding window concept is a repeatable pattern that is used in various types of problems in algorithmic programming. It allows us to perform an operation on all contiguous substrings or subarrays of a string or array in an efficient way.
- The pattern of adding an element to a data structure when expanding the window and removing an element when shrinking the window is a key pattern in sliding window problems.
- Keeping track of the maximum value found so far is another common pattern in many problems.

Solution Approach and Analysis

Let’s use the metaphor of a window moving along the length of a wall covered with painted symbols. The wall represents the input string s and each symbol corresponds to a character in s. The window can only accommodate k distinct symbols at any given time and we are tasked to find the longest portion of the wall (or segment of the string) where the window can comfortably “fit”.

Step 1 - Initial Setup

We need two pointers left and right to represent the left and right edges of our window. Let’s initialize them at the beginning of the wall (i.e., the start of the string).
We need a char_count dictionary to keep track of the count of each distinct symbol (character) that is currently within the window.
Lastly, we need a max_length variable to keep track of the longest segment of the wall (substring) where our window has been able to fit. This is initially set to zero.

Step 2 - Move the Window

We move our window to the right by increasing the right pointer. For every new symbol (character s[right]) that falls within our window, we increase its count in the char_count dictionary.
If at any point, our window has more than k distinct symbols, we need to move the left edge of the window to the right. This is done by decreasing the count of the symbol (character s[left]) in the char_count dictionary and then increasing left until we again have k or fewer distinct symbols within the window.
After adjusting the window at each step, we calculate its length (right - left + 1) and update our max_length variable if this length is greater than the current max_length.

Step 3 - Return the Result

After moving the window all the way to the right end of the wall (the end of the string), the longest segment where the window fit (the longest substring with at most k distinct characters) will be the length stored in max_length. So, we return max_length.

Effects of Changing Problem’s Parameters

If k is increased, the window can accommodate more distinct symbols, thus the longest valid segment may increase or stay the same.
If k is decreased, the window becomes stricter about the distinct symbols it can accommodate, thus the longest valid segment may decrease or stay the same.

Demonstration

Let’s use the example where s = "eceba" and k = 2.

At the beginning, left = 0, right = 0, max_length = 0, char_count = {}.
We move right to 1 (covering “ec”). Now we have two distinct characters, so we continue moving right.
At right = 2, our window covers “ece”, and we still have only two distinct characters. So, we update max_length = 3.
When right moves to 3, our window (“eceb”) has 3 distinct characters, which is more than k. So, we move left to 1 and our window becomes “ceb”.
Then we move right to 4 (the end), and our window (“ceba”) again has more than k distinct characters. We need to move left to 2, and our window becomes “eba”.
Now we’ve reached the end of the string and our max_length remains 3, which is the length of the longest substring with at most 2 distinct characters (“ece”). So, we return 3.

Identify Invariant

An invariant, in the context of algorithms, is a condition that remains unchanged throughout the execution of the algorithm.

In this problem, the invariant is that at any point during the processing of the string s, the substring from index left to right in s (the current “window”) contains at most k distinct characters.

This invariant holds because whenever we extend the window by moving the right pointer, we check the number of distinct characters in the window. If it exceeds k, we immediately adjust the left pointer to reduce the number of distinct characters back down to k or less. Therefore, at the end of each step in our main loop, the window always contains at most k distinct characters.

Maintaining this invariant is crucial to the algorithm because it ensures that we are always considering valid substrings as per the problem’s requirements, allowing us to accurately compute the maximum length of such a substring.

Identify Loop Invariant

A loop invariant in computer science is a condition that is initially true and remains true after each iteration of a loop.

In this problem, the loop invariant within the main processing loop of the string s is that the substring from the left index to the right index (or the current “window”) will always contain at most k distinct characters.

This loop invariant holds true because as we iterate through the string by moving the right pointer, we immediately adjust the left pointer to reduce the number of distinct characters to k or less if it exceeds k after moving the right pointer.

So, at the end of each loop iteration, our window always satisfies the condition of having at most k distinct characters. This loop invariant is crucial to our solution, as it ensures that we are always considering valid substrings as per the problem’s requirements, allowing us to compute the maximum length of such a substring accurately.

In the context of this problem, the concepts of invariant and loop invariant can be considered essentially the same. Both are conditions that remain unaltered during the execution of the program. However, in a broader context, they have distinct meanings.

An “invariant” is a condition that holds true in a certain context or part of a program. This context could be the entire program, a certain data structure, or a section of the code. The concept of an invariant is used to reason about the correctness of a program.

On the other hand, a “loop invariant” is a specific type of invariant that remains true from iteration to iteration of a loop. It is an assertion, which if it’s true before an iteration of a loop, remains true before the next iteration. It’s often used for proving the correctness of an algorithm.

In this problem, the invariant is indeed the same as the loop invariant because the primary logical operation is happening within the loop, and that’s where our invariant condition is validated and maintained.

Thought Process

The problem is about finding the longest substring that contains at most k distinct characters from a given string s.

Here are the key insights and steps to solve the problem:

Understanding the Problem: The first step is to thoroughly understand what the problem is asking for. We are asked to find the longest substring from a given string that contains at most k distinct characters.
Identify the Problem Type: This problem is a sliding window problem. The cues in the problem statement that hint at this are the words ‘substring’ and ‘at most k distinct characters’. In a sliding window problem, we have a window of some size and we slide it over our input to analyze some property of the window.
Strategy: Our approach will be to keep expanding our window to the right (increasing j) until we have more than k distinct characters in our window. If we exceed k distinct characters, we will start to decrease our window size from the left (increasing i) until we have at most k distinct characters. We will keep track of the maximum size of our window, which corresponds to the length of the longest substring with at most k distinct characters.
Implementing the Solution:

Here’s the Python code to solve the problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0

        i, max_len = 0, 0
        char_count = {}

        for j in range(len(s)):
            if s[j] not in char_count:
                char_count[s[j]] = 0
            char_count[s[j]] += 1

            while len(char_count) > k:
                char_count[s[i]] -= 1
                if char_count[s[i]] == 0:
                    del char_count[s[i]]
                i += 1

            max_len = max(max_len, j - i + 1)

        return max_len

In this code, char_count is a dictionary used to keep track of the count of each character in the current window. i and j are the left and right boundaries of the current window respectively. max_len is used to keep track of the maximum length of the substring we’ve found that satisfies the condition.

Establishing Preconditions and Postconditions

Parameters:
- The inputs to the method are a string s and an integer k.
- s is a string which represents the sequence of characters we are looking at. k is an integer that represents the maximum number of distinct characters we are allowed in a substring.
- Within the context of the problem, s is the string from which we are finding substrings and k is the constraint for the maximum number of distinct characters allowed within a substring.
Preconditions:
- The string s must not be null and k must be a non-negative integer.
- The length of string s must be within the range [1, 5 * 10^4] and k within the range [0, 50] as per the problem constraints.
- There isn’t a specific state the program must be in prior to calling the method.
Method Functionality:
- This method is expected to find and return the length of the longest substring of s that contains at most k distinct characters.
- The method does not change the state of the program or modify its inputs. It uses the inputs to calculate and return the desired value.
Postconditions:
- After the method has returned, the state of the program and the values of the parameters remain unchanged.
- The return value represents the length of the longest substring of s that contains at most k distinct characters.
- The method does not have any side effects as it does not change the state of the program or modify its inputs.
Error Handling:
- If the preconditions are not met (for example, if s is null or k is negative), the method’s behavior is not defined in the problem statement. In practice, you might choose to throw an exception or return a special value (like -1) to indicate that an error occurred. However, this will depend on the specific requirements of your application and how it is supposed to handle errors. In a competitive programming context like LeetCode, you generally assume that the inputs will always meet the problem’s constraints.

Problem Decomposition

Problem Understanding:
- The problem is about finding the longest substring from a given string that contains at most a certain number of distinct characters. The length of this longest substring is what we need to return.
Initial Breakdown:
- The problem can be broken down into two major subproblems:
  1. Identifying all possible substrings of the given string.
  2. Checking if a substring contains at most ‘k’ distinct characters and if it does, keeping track of the longest such substring.
Subproblem Refinement:
- Identifying all possible substrings: This can be done by starting with each character in the string as a starting point and progressively including more characters in the substring.
- Checking if a substring contains at most ‘k’ distinct characters: This involves keeping a count of distinct characters in a substring and verifying it doesn’t exceed ‘k’. If it does, we need to shrink the substring from the beginning until it meets the condition again.
Task Identification:
- There are two repeated tasks in this process:
  1. Expanding the substring by moving the end index forward.
  2. Shrinking the substring by moving the start index forward.
Task Abstraction:
- “Expanding the substring” involves adding a character to the substring and updating the count of distinct characters.
- “Shrinking the substring” involves removing characters from the start of the substring and updating the count of distinct characters.
Method Naming:
- We could name the tasks as expandSubstring and shrinkSubstring.
Subproblem Interactions:
- These tasks are interdependent. We can only shrink a substring after expanding it. And we may need to expand it again after shrinking. The process continues in a loop until we’ve traversed the entire string. The order of operations is dictated by the condition whether the current substring meets the ‘k’ distinct characters requirement or not.

From Brute Force to Optimal Solution

Brute Force Solution:

Generate all possible substrings of the given string. There are approximately n^2 substrings where n is the length of the string.
For each substring, count the number of distinct characters.
If the number of distinct characters is less than or equal to ‘k’, check if the length of this substring is greater than the longest valid substring found so far. If so, update the maximum length.

This brute force solution is simple to understand and implement. However, it is inefficient. It has a time complexity of O(n^2 * m) where n is the length of the string, and m is the average length of the substrings. This is because for each of the n^2 substrings, we are counting the distinct characters which take O(m) time. The space complexity is O(1) as we’re using only a constant amount of space to store the maximum length and temporary variables.

Optimized Solution Using Sliding Window:

Rather than checking all substrings, we can use a “sliding window” approach to efficiently find the longest substring with at most k distinct characters.

Start by initializing two pointers, start and end, at the beginning of the string. These pointers define the current substring we’re considering.
Extend the end pointer character by character forward in the string.
Keep track of the counts of each character in the current substring using a hash map.
If the number of distinct characters in the current substring exceeds k (which we can check by the size of our hash map), then we know we need to move the start pointer forward to reduce the number of distinct characters. Keep moving the start pointer forward, decrementing the count of the characters you pass in the hash map, until you’re back to k distinct characters.
At each point (each unique position of the end pointer), check if the current substring (from the start pointer to the end pointer) is longer than the current longest substring you’ve found. If so, update your longest substring.
Continue this process until the end pointer has moved to the end of the string. The longest substring you’ve found at this point is your result.

The time complexity of the optimized solution is O(n) because each character in the string is visited at most twice by the start and end pointers. The space complexity is O(k) for the hash map that is used to keep track of characters’ counts. In the worst-case scenario where k is equal to n (the length of the string), the space complexity is O(n).

Code Explanation and Design Decisions

Initial parameters: The initial parameters for the function are the string s and an integer k. s represents the given string where we need to find the longest substring with at most k distinct characters. k is the maximum number of distinct characters that the longest substring can contain.
Primary loop/iteration: The primary iteration is a loop over each character in the string s. Each iteration represents an extension of the current substring by adding a new character at the end pointer of the substring.
Conditions/Branches: There’s a key condition inside the loop: if the number of distinct characters in the current substring (represented by the size of the hash map) exceeds k, it means we need to move the start pointer forward to drop some characters and decrease the number of distinct characters.
Updates/Modifications: Within each iteration, the end pointer is advanced to increase the length of the current substring. If the number of distinct characters exceeds k, the start pointer is also moved forward until we’re back to k distinct characters. In addition, the hash map is updated to keep track of the character counts in the current substring.
Invariant: The invariant in the code is that the substring between the start and end pointers will always contain at most k distinct characters. This invariant is necessary to ensure we are always considering valid substrings according to the problem’s constraints.
Final output: The final output of the function is the length of the longest valid substring found during the iterations. It represents the maximum length of a substring in s that contains at most k distinct characters, and thus directly answers the problem statement.

Coding Constructs

High-level problem-solving strategies: This code primarily uses a “sliding window” technique, with two pointers marking the start and end of a window that slides through the string. It also uses a hash map to keep track of the counts of characters in the current window.
Purpose of the code to a non-programmer: This code is trying to find the longest continuous part of a string that has a certain maximum number of different letters. It’s like going through a list of letters and trying to find the longest section where you only see a certain number of different letters.
Logical elements or constructs: The main logical elements in this code are the loops and conditional statements. The loops are used to move through the string, and the conditional statements are used to check whether the current section of the string meets the problem’s constraints.
Algorithmic approach in plain English: The code starts at the beginning of the string and keeps moving forward, adding letters to a current section, until the number of different letters in that section becomes more than allowed. At that point, it starts dropping letters from the beginning of the section until it’s back within the allowed limit. While doing this, it keeps track of the longest section it has found so far, and that’s the final answer.
Key steps or operations: The key operations this code is performing include iterating over the characters in the string, maintaining a running count of characters in the current window (substring) using a hash map, checking the condition (whether the count of distinct characters exceeds k), adjusting the window size based on the condition, and keeping track of the maximum length of a valid window.
Algorithmic patterns or strategies: The main algorithmic pattern used here is the “sliding window” pattern, where a window of items is maintained and the window “slides” through the data structure being processed (the string, in this case). This pattern is often used in array or string processing problems where a contiguous segment of the data structure needs to be analyzed.

Language Agnostic Coding Drills

Concept Dissection:
- Looping through a string: This concept involves iterating through each character in a string. This is a basic operation in string processing.
- Using a Hash Map: This concept involves using a hash map (or dictionary) to keep track of the count of characters. This is a commonly used data structure for keeping counts or maintaining other forms of relationships.
- Maintaining a Sliding Window: This concept involves keeping a moving window of characters within a string and adjusting the start and end points of the window based on certain conditions. This requires a good understanding of manipulating indices.
- Updating Maximum Value: This concept involves keeping track of a maximum value (in this case, the maximum length of substring) and updating it whenever a larger value is found.
Difficulty Classification:
- Easy: Looping through a string. It’s one of the basic constructs in programming, understanding and using this concept is often a fundamental requirement in many programming tasks.
- Medium: Using a Hash Map. This involves understanding a more complex data structure, and how to use it to track counts or relationships.
- Hard: Maintaining a Sliding Window. This concept is slightly more advanced as it involves manipulating indices based on certain conditions, which requires careful consideration to avoid errors.
- Medium: Updating Maximum Value. This involves keeping track of the largest value found so far, a concept that isn’t as difficult as maintaining a sliding window but more complex than a simple loop.
Problem-Solving Approach:
- The problem-solving process begins with reading and understanding the problem statement. The initial observation is that we need to find a substring with certain properties, which suggests the use of a sliding window approach.
- We start with defining a window within the string and maintaining this window such that the number of distinct characters inside it does not exceed k. For each character in the string, we extend the window to include it and update our count of characters using a hash map.
- When we find that the number of distinct characters in our window exceeds k, we shrink the window from the left until we’re back within the allowed limit.
- During this process, for every valid window (i.e., a window with k or fewer distinct characters), we compare its length with the maximum length seen so far. If it’s longer, we update the maximum length.
- This process continues until we’ve iterated through every character in the string. The maintained maximum length of a valid window will be our answer.

Targeted Drills in Python

Concept Drills

Looping through a string in Python

1
2
3
s = "hello"
for char in s:
    print(char)

This simple Python code snippet shows how to iterate through each character in a string.

Using a Hash Map in Python

1
2
3
4
5
6
7
8
s = "hello"
char_count = {}
for char in s:
    if char in char_count:
        char_count[char] += 1
    else:
        char_count[char] = 1
print(char_count)

Here we are using a Python dictionary as a hash map to count the occurrence of each character in the string.

Maintaining a Sliding Window in Python

1
2
3
4
5
6
s = "hello"
window_start = 0
window_end = 0
for window_end in range(len(s)):
    # Perform necessary operations
    pass

This code outlines the structure of a sliding window in Python, where window_start and window_end are the start and end indices of the window.

Updating Maximum Value in Python

1
2
3
4
5
6
values = [1, 2, 5, 3, 7, 8, 4]
max_value = 0
for value in values:
    if value > max_value:
        max_value = value
print(max_value)

This Python code demonstrates how to find and update the maximum value in a list of numbers.

Problem-Specific Concept Drills

Maintaining a Sliding Window of Distinct Characters in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
s = "abcabcabc"
k = 2
char_count = {}
window_start = 0
max_length = 0
for window_end in range(len(s)):
    if s[window_end] not in char_count:
        char_count[s[window_end]] = 0
    char_count[s[window_end]] += 1

    while len(char_count) > k:
        char_count[s[window_start]] -= 1
        if char_count[s[window_start]] == 0:
            del char_count[s[window_start]]
        window_start += 1

    max_length = max(max_length, window_end-window_start+1)
print(max_length)

This code shows a sliding window of distinct characters, the heart of the problem’s solution. Here, the char_count dictionary is keeping track of character counts, window_start is being updated to maintain k distinct characters in the window, and max_length is being updated with the maximum length of such a window.

Integration
We’ve actually already integrated these concepts in the last drill. The code for maintaining a sliding window of distinct characters combines the following concepts:
- Looping through the string using a for loop.
- Using a hash map to keep track of the counts of distinct characters within the sliding window.
- Implementing a sliding window by maintaining window_start and window_end pointers.
- Updating a maximum value to keep track of the longest substring found.
Hence, each of these drills contributes to building up the final solution. The last drill encapsulates the complete solution for the problem.

Q&A

I developed some intuition by solving a few problems of Dynamic Programming … that the Longest Common subsequence (and some similar problems) can be handled nicely using Dynamic Programming. (Also LCS is discussed in great detail in Intro to Algo book [Cormen et. al])

Given you face this in an interview, how to think that it is not DP and that another linear time algorithm is possible. Right now I was able to do it since I couldn’t come up with a proper recurrence (but to convince myself there is no DP recurrence possible, I had to spend a lot of time!)

Dynamic programming (DP) is indeed a powerful tool and is applicable to a vast number of problems, especially those involving sequences and arrays. However, not all problems that initially appear to be suited for a DP solution actually require one.

While the Longest Common Subsequence (LCS) problem is a classic example of a problem solvable via dynamic programming, the problem of finding the longest substring with at most K distinct characters isn’t necessarily a candidate for DP. Here’s why:

Overlapping Subproblems and Optimal Substructure: Dynamic programming works well when a problem has both overlapping subproblems (the same problem is solved multiple times) and an optimal substructure (an optimal solution can be constructed from optimal solutions of its subproblems). Although our problem does involve subproblems, they do not overlap in the same way that a problem like LCS does, nor does it have a clear optimal substructure.
Subproblem Dependency: In the longest substring with at most K distinct characters problem, we’re asked for a substring (consecutive characters), not a subsequence (doesn’t have to be consecutive). This is a key distinction because, in a substring problem like this, the current character’s status (whether it is included in the longest substring) depends heavily on the previous characters, especially those within the same substring. The dependency of subproblems in this case is much more localized than in problems where DP would be a good fit.
Space and Time Complexity: A dynamic programming approach would likely result in time and space complexity of O(n^2), which can be inefficient for large inputs. By contrast, a sliding window approach achieves a linear time complexity of O(n) and a space complexity of O(k), making it much more efficient.

As for developing an intuition about whether DP is appropriate, that largely comes with experience. Practice with a variety of problem types will help you recognize the characteristics of problems that lend themselves to certain strategies. It’s also important to realize that multiple approaches can often solve a single problem, and part of the skill in problem-solving is recognizing which approach is most efficient or elegant for the problem at hand.

Whenever I’m asked for the longest subsequence of something, my first thought it always some sort of sliding window. In this case it’s pretty easy and linear, because each letter is either 1) already in the window; 2) new but not causing the unique characters to overflow; or 3) new but causing the unique characters to overflow. Based on which case the new letter causes we can figure out how to move the left side of the window.

That’s an excellent approach! You’re absolutely right. The sliding window strategy is particularly useful in problems where you need to find a subarray or substring that meets certain conditions, such as this one.

Here’s a breakdown of your approach:

Initialize the window: Start with a window that includes only the first character of the string.
Expand the window: Iteratively add the next character in the string to the window. There are three cases here:
a. The character is already in the window: In this case, simply expand the window to include the new character.
b. The character is not in the window, but adding it doesn’t exceed the maximum number of unique characters (K): Again, simply expand the window to include the new character.
c. The character is not in the window, and adding it would exceed the maximum number of unique characters (K): In this case, you need to shrink the window from the left until adding the new character wouldn’t exceed K unique characters.
Update the maximum length: After each expansion (and potential contraction), compare the length of the current window to the maximum length seen so far. If the current window is longer, update the maximum length.
Repeat until the window can no longer be expanded: Continue expanding and potentially contracting the window until you’ve processed every character in the string.

This approach ensures that you’re always working with a valid substring (i.e., a substring with K or fewer unique characters), and that you’re checking every possible valid substring by moving the window across the entire string. As a result, you can be sure that you’ve found the maximum length possible for a valid substring.

Simple explanation:

We can resize the window to maintain the invariant. The counter is used to count each type of character within the window. If the current window is valid, we expand the window by moving the right edge by one. If the window is invalid, we move the left edge by one. This discards the character from our window. We have to keep shrinking the window until it becomes valid. During this process, we keep track of the longest valid window we have seen so far.