340. Longest Substring with At Most K Distinct Characters

Problem Description

In this problem, we are given a string s and an integer k. Our task is to find the length of the longest substring (which is a contiguous block of characters in the string) within s that contains at most k distinct characters.

A distinct character means that no matter how many times the character appears in the substring, it is counted only once. For example, if k = 2, the substring "aabbc" has 3 distinct characters ('a', 'b', and 'c'), thus, it does not meet the requirement.

The goal here is to achieve this while maximizing the length of the substring. A substring could range from containing a single character up to the length of the entire string, if k is sufficiently large to cover all distinct characters in the string s.

Intuition

The core intuition behind the solution is to use the two-pointer technique, or more specifically, the sliding window approach. Here is the thinking process that leads us to this approach:

1. We need to examine various substrings of s efficiently without having to re-scan the string repeatedly.
2. We can start with a window (or two pointers) at the beginning of the string and expand the window to the right until we exceed k distinct characters within the window.
3. Upon exceeding k distinct characters, we need to move the left side of the window to the right to potentially drop one of the distinct characters out of the count.
4. We keep track of the count of distinct characters in the current window using a data structure, such as a counter (dictionary), that is updated when the window is adjusted.
5. As we expand and contract the window, we keep a record of the maximum window size (i.e., substring length) that has appeared so far that contains at most k distinct characters. This is the number we want to return.

Now, the implementation uses a counter and two indices, i and j, where i is the end of the sliding window, and j is the start. We iterate over the string with i:

• We include the character at position i in the current window by incrementing its count in the counter.
• If adding the current character has led to more than k distinct characters in the window, we increment j, effectively reducing the size of the window from the left, until the number of distinct characters drops to k or lower.
• At each step, we calculate the length of the current window (i - j + 1) and update the answer if it's the largest such length we have seen so far.
• This process continues until i has reached the end of the string.

The sliding window is moved across the string efficiently to identify the longest substring that satisfies the condition of having at most k distinct characters, thus leading us to the solution.

Learn more about Sliding Window patterns.

Solution Approach

The solution code implements the sliding window pattern using two pointers to keep track of the current window within the string s. This pattern is completed using the Python Counter from the collections module as the key data structure to keep counts of each character in the current window.

Here is how it is done step by step:

1. We initialize a Counter object, which is a dictionary that will keep track of the counts of individual characters in the current sliding window.

2. Two pointers, i and j, are created. i is used to traverse the string s character by character from the start to the end, while j is used to keep track of the start of the sliding window. j starts at 0 and moves rightward to narrow the window whenever necessary.

3. We initialize a variable ans to keep track of the maximum length of the substring found that meets the criteria.

4. We start iterating over the characters of the string s, with i acting as the end boundary of the window. For each character c at index i, we:

   • Increment its count in the Counter by 1 (cnt[c] += 1).

   • Check if the number of distinct characters in the Counter has exceeded k. This is done by evaluating len(cnt) > k. As long as this condition is true, meaning we have more than k distinct characters, we need to shrink the window from the left side by increasing j.

     • In the inner while loop, decrease the count of the character at the beginning of the window (cnt[s[j]] -= 1).
     • If the count of that character drops to 0, we remove it from the Counter (cnt.pop(s[j])), as it's no longer part of the window.
     • We increment j to shrink the window from the left.

5. After adjusting the size of the window (if it was needed), we calculate the length of the current window (i - j + 1) and update ans to be the maximum of its current value and this newly calculated length.

6. After iterating through all characters of s, the process concludes, and the final value of ans contains the length of the longest substring with at most k distinct characters. This value is returned as the result.

Through this method, we avoid unnecessary re-scans of the string and implement an O(n) time complexity algorithm, where n is the length of the string s. By dynamically adjusting the sliding window and using the Counter to track distinct characters, we achieve an efficient approach to solving the problem as outlined.

Example Walkthrough

Let's assume we have a string s = "aabcabb", and the integer k = 2. We want to find the length of the longest substring with at most k distinct characters.

Here is a step-by-step walkthrough of the solution approach applied to this example:

1. Initialize the Counter and Pointers: Create a Counter object, cnt, to count characters in the current window. Set i, j to 0 to represent the start and end of the sliding window, and ans to 0 as the longest substring length found so far.

2. Start Iterating with Pointer i: Move i from the start to the end of the string s.

   i = 0: cnt = {'a': 1}, substring is a, ans = 1.

   i = 1: cnt = {'a': 2}, substring is aa, ans = 2.

   i = 2: cnt = {'a': 2, 'b': 1}, substring is aab, ans = 3.

3. Exceeding k Distinct Characters: At the next character, we check if the number of distinct characters will exceed k.

   i = 3: We attempt to insert c into cnt. Doing so would increase distinct character count to 3 (cnt = {'a': 2, 'b': 1, 'c': 1}), which is greater than k. We need to move j right until we get at most k distinct characters.

4. Shrinking the Window:

   Start incrementing j, decreasing the count of the character s[j] in cnt, and remove the character from cnt if its count reaches 0.

   j = 1: We decrease the count of a and update cnt = {'a': 1, 'b': 1, 'c': 1}. We still have more than k distinct characters.

   j = 2: We decrease the count of a and remove it from cnt (cnt = {'b': 1, 'c': 1}). Now we have k distinct characters.

   After shrinking, the substring is now bc (s[2:4]), and ans remains 3.

5. Continue Process:

   i = 4: Add a to cnt, cnt = {'b': 1, 'c': 1, 'a': 1}, substring is bca, ans remains 3.

   i = 5: Add b to cnt, cnt = {'b': 2, 'c': 1, 'a': 1}. We have exceeded k again, so start moving j.

   j = 3: Reduce count of b, cnt = {'b': 1, 'c': 1, 'a': 1}. Still too many distinct characters.

   j = 4: Remove c, cnt = {'b': 1, 'a': 1}, and now the substring is ab (s[4:6]), update ans to 2.

   i = 6: Add b, cnt = {'b': 2, 'a': 1}, and substring is abb (s[4:7]). Now, update ans to 3, as this is the length of the current window.

6. Finish Iteration:

   After the final iteration, ans contains the length of the longest satisfactory substring, which is 3 in this case, representing the substring aab or abb.

By using the sliding window technique, the algorithm efficiently finds the longest substring that satisfies the given constraint with a time complexity of O(n), where n is the length of the string s.

Solution Implementation

Time and Space Complexity

The given code snippet defines a function that determines the length of the longest substring with no more than k distinct characters in a given string s.

Time Complexity

The time complexity of the function can be analyzed as follows:

• There are two pointers (i and j) that traverse the string s only once. The outer loop runs for all characters from position 0 to n - 1 where n is the length of the string s, hence contributing O(n) to the time complexity.
• Inside the loop, there is a while loop that shrinks the sliding window from the left when the number of distinct characters exceeds k. This while loop does not run for each element in s multiple times. Each character is removed from the window only once, accounting for another O(n) over the whole run of the algorithm.

Therefore, the total time complexity of the algorithm is O(n) where n is the number of characters in the input string s.

Space Complexity

The space complexity of the function can be analyzed as follows:

• A Counter object is used to keep track of the frequency of each character in the current window. In the worst case, the counter could store a distinct count for every character in the string s. However, since the number of distinct characters is limited by k, the Counter would hold at most k elements.

Therefore, the space complexity of the algorithm is O(k) where k is the maximum number of distinct characters that the substring can have.

Learn more about how to find time and space complexity quickly using problem constraints.