You are given a string s and an integer k. Write a function to find the length of the…
- User
You are given a string
sand an integerk. Write a function to find the length of the longest substring ofsthat contains at mostkdistinct characters. Please this is a sliding window problem, write a function that solves this problem, and explain your algorithm. - Assistant
We are given a string
sand an integerk. We need to find the length of the longest substring that contains at mostkdistinct characters. This is a classic sliding window problem. We can use a hash map (or dictionary) to keep track of the character counts in the current window. We maintain a window [left, right] that we expand by moving right pointer. We add the character at right to the map. If the map size exceeds k (meaning we have more than k distinct characters in the window), we need to shrink the window from the left until we have at most k distinct. While shrinking, we decrement the count of the left character and remove it if count becomes 0. We update the maximum length whenever we have a window with at most k distinct.Steps:
- Initialize left = 0, max_len = 0.
- Use a dictionary (or defaultdict) to store character counts in the current window.
- Iterate right from 0 to len(s)-1: a. Add s[right] to the dictionary (increment count). b. While the number of keys in the dictionary > k: i. Decrement count of s[left] in the dictionary. ii. If the count becomes 0, remove the key from the dictionary. iii. Increment left. c. Now the window [left, right] has at most k distinct characters, update max_len = max(max_len, right-left+1)
- Return max_len.
However, note that we want at most k distinct, so we update the max_len when the condition is satisfied (i.e., after the inner while loop, we have <=k distinct).
But note: the inner while loop runs until we have <=k distinct. Then we are safe to update.
Alternatively, we can update max_len only when the window is valid (<=k distinct). But note that after the inner while loop, we have a valid window.
Let's code accordingly.
Example: s = "eceba", k = 2 We expect 3 ("ece").
Another approach: we can update max_len at every step after adjusting the window? Actually, we want the maximum window size that satisfies the condition. Since we are shrinking until the condition is satisfied, the current window [left, right] is the largest window ending at right that satisfies the condition? Not exactly: because we might have shrunk too much? But we only shrink when necessary, and we stop as soon as we have <=k. So the current window is the maximum window ending at right that satisfies the condition.
However, note that we are updating max_len after the inner while loop, meaning we are considering the window that just became valid. But wait, what if we never exceeded k? Then we didn't enter the while loop and we update with the current window which is valid.
So the algorithm:
left = 0 max_len = 0 char_count = {}
for right in range(len(s)): char = s[right] char_count[char] = char_count.get(char, 0) + 1
while len(char_count) > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: del char_count[left_char] left += 1 # Now the window [left, right] has at most k distinct max_len = max(max_len, right - left + 1)return max_len
But wait, what if k is 0? Then we are looking for substring with at most 0 distinct characters, which is an empty substring. However, note that the problem says at most k, so k=0 means we can have 0 distinct, which is empty string. But our algorithm would return 0? Because we never update max_len? Let's see:
If k=0, then when we add the first character, we have 1 distinct, then we enter the while loop and remove it, so left becomes 1 and the window is of length 0. Then we update max_len = max(0, 0) -> 0. So it's correct.
However, note that the problem says "at most k distinct", so if k=0, we cannot have any character. So the longest substring is the empty string, length 0.
But what about when k is greater than or equal to the total distinct characters in s? Then we can have the entire string, so we return len(s).
Let's test with s="aa", k=1: right=0: char_count={'a':1}, len=1 <=1 -> max_len=1 right=1: char_count={'a':2}, len=1 <=1 -> max_len=2
So it works.
However, note that the inner while loop condition is while the number of distinct characters > k. So we are ensuring that after the loop, we have <=k.
But what if k is negative? The problem states integer k, but typically k is non-negative. We can assume k>=0.
Let's write the function accordingly.
However, note that the above algorithm updates max_len for every right, even if we just shrunk. But note: after the inner while loop, the window [left, right] is the maximum window ending at right that satisfies the condition? Actually, it's the minimal left for this right such that the window has <=k distinct. But we want the maximum length, and for a fixed right, the minimal left (i.e., the largest window) is what we want? Wait, we are moving right and for each right we are adjusting left to the smallest index such that [left, right] has <=k distinct. Then the window [left, right] is the largest window ending at right that satisfies the condition?
Let me think: For a fixed right, we want the longest window ending at right that has at most k distinct. That would be the smallest left such that [left, right] has at most k distinct. Because if we move left further left, we might add a distinct character and break the condition. So indeed, we are computing for each right the minimal left that makes the window valid, and then the window [left, right] is the largest valid window ending at right.
Therefore, we can update max_len with the current window size.
But note: the inner while loop may run multiple times, and after each iteration of the for loop (for each right) we have a valid window. So we update.
However, there is an alternative: we can update max_len only when we have a valid window without entering the while loop? But we also update after the while loop, which is when we have a valid window.
This algorithm runs in O(n) time because each character is added and removed at most once. The inner while loop does not cause O(n^2) because left only moves forward.
Let's code accordingly.
But wait: what if we have k=2 and s="abcabcbb"? The longest substring with at most 2 distinct is "bca" (length 3) or "abc" (length 3)? Actually, for at most 2 distinct, the longest is "ab" (2) or "bc" (2) or "ca" (2) ... wait, let's see:
s = "abcabcbb", k=2: We can have "abc" -> 3 distinct? No, 3. So not allowed. "ab" -> 2, length 2. "bc" -> 2, length 2. "ca" -> 2, length 2. "abca" -> 3 distinct (a,b,c) -> not allowed. Actually, the longest substring with at most 2 distinct is "abc" is not allowed because 3 distinct. So we look for "abca"? No. How about "bcab"? 3 distinct? Let's list: from index 0: "a" -> 1, "ab" -> 2, "abc" -> 3 -> too many. So max from index0 is 2. from index1: "b","bc","bca" -> 3 distinct? b,c,a -> 3. So max from index1 is 2 ("bc"). from index2: "c","ca","cab" -> 3 distinct? c,a,b -> 3. So max from index2 is 2. from index3: "a","ab","abc" -> 3 again. from index4: "b","bc","bcb" -> 2 distinct? b,c -> 2, and then "bcbb" -> 2? b,c -> 2? Actually, "bcbb" has b and c, 2 distinct. So length 4? Wait, from index4: index4: 'b' index5: 'c' -> 2 index6: 'b' -> 2 index7: 'b' -> 2 So "bcbb" has 2 distinct? Actually, it has b and c. So length 4. So the longest is 4? But wait, we have to check if there's longer.
Let's try from index5: index5: 'c' ->1 index6: 'b' ->2 index7: 'b' ->2 -> length 3? (cbb) but that's less than 4. So the longest is 4? But wait, the substring "bcbb" is from index4 to index7? That's 4 characters. And it has 2 distinct (b and c). So the answer should be 4. Now run the algorithm: left=0, max_len=0 right=0: char='a', char_count={'a':1} -> distinct=1 <=2 -> max_len=1 right=1: char='b', char_count={'a':1, 'b':1} -> distinct=2 <=2 -> max_len=2 right=2: char='c', char_count={'a':1, 'b':1, 'c':1} -> distinct=3>2 -> enter while: left_char='a', char_count['a']=0 -> remove 'a', left=1, char_count={'b':1, 'c':1} -> distinct=2, exit while. then max_len = max(2, 2-1+1=2) -> 2. right=3: char='a', char_count={'b':1, 'c':1, 'a':1} -> distinct=3>2 -> while: left_char='b', char_count['b']=0 -> remove 'b', left=2, char_count={'c':1, 'a':1} -> distinct=2, exit while. then max_len = max(2, 3-2+1=2) -> 2. right=4: char='b', char_count={'c':1, 'a':1, 'b':1} -> distinct=3>2 -> while: left_char='c', char_count['c']=0 -> remove 'c', left=3, char_count={'a':1, 'b':1} -> distinct=2, exit while. then max_len = max(2, 4-3+1=2) -> 2. right=5: char='c', char_count={'a':1, 'b':1, 'c':1} -> distinct=3>2 -> while: left_char='a', char_count['a']=0 -> remove 'a', left=4, char_count={'b':1, 'c':1} -> distinct=2, exit while. then max_len = max(2, 5-4+1=2) -> 2. right=6: char='b', char_count={'b':2, 'c':1} -> distinct=2 <=2 -> no while. max_len = max(2, 6-4+1=3) -> 3. right=7: char='b', char_count={'b':3, 'c':1} -> distinct=2 <=2 -> no while. max_len = max(3, 7-4+1=4) -> 4. So it returns 4, which is correct.But wait, why at right=6 we have left=4? Because after right=5 we had left=4 and the window was [4,5] which is "bc". Then at right=6, we add 'b' and the window becomes [4,6] which is "bcb", distinct=2. Then at right=7, we add 'b' and it becomes "bcbb", distinct=2.
So the algorithm works.
However, note that the inner while loop condition is checked after every addition. We are ensuring that after the inner while, we have at most k distinct.
But what about the case when k is 0? We already considered.
Let's code accordingly.
However, note: the problem says "at most k", so k can be 0. Our algorithm handles it.
But what if k is larger than the number of distinct characters in the entire string? Then we will never enter the while loop and the window will be the entire string.
So it's correct.
Let's write the function.
We assume s is a string and k is an integer.
Edge cases: s empty? Then return 0. k=0? Then return 0 (since we cannot have any character).
But note: if s is empty, then the loop doesn't run and we return 0.
Let's code.
However, note that the problem does not specify that k is non-negative? But if k is negative, then we cannot have any substring with at most negative distinct? So we return 0? But the problem says integer k, so we should handle negative? Typically k is non-negative. We can add a check: if k < 0: return 0.
But the problem says at most k, and if k is negative, then we cannot have any substring because the number of distinct characters is always non-negative. So we return 0.
Let's adjust: if k < 0: return 0.
But the problem says integer k, so it could be negative.
We'll do:
if k < 0: return 0
However, note that the inner while loop condition is len(char_count) > k. If k is negative, then we start with an empty window? But we are adding a character and then the condition becomes 1 > negative -> true, so we will try to shrink. But left starts at 0 and we are at right=0, then we remove the left character (which is the same as the one we just added) and then left becomes 1, and the window becomes [1,0] which is invalid (left>right). Then we update max_len? But note: after the while loop, we have left=1 and right=0, so the window length is 0. Then we update max_len=0. Then next right=1, we add s[1] and then again we have 1 distinct and condition 1>k (negative) -> true, so we remove s[1]? But wait, the window is [1,1] and we remove s[1] and then left=2, and so on. So we never update max_len to anything but 0. So it returns 0.
So we can handle negative k by the same algorithm? But note that if k is negative, we cannot have any valid non-empty window. So we return 0.
However, the algorithm above would work for negative k? Let's test with k=-1 and s="a":
left=0, max_len=0 right=0: char='a', char_count={'a':1} -> distinct=1 > -1 -> enter while: remove s[0] -> char_count['a']=0 -> remove key, left=1. Now window [1,0] -> length 0. Then update max_len = max(0, 0-1+1=0) -> 0.
Then return 0.
So it works.
But we can also add an early check for k<0 to avoid unnecessary work? It's optional.
Let's code without the early check and it will work.
However, note that the condition in the while is
len(char_count) > k. If k is negative, then even an empty window (distinct=0) is not > k? Wait, 0 > -1? Yes, 0 is greater than -1. So for an empty window, we would not enter the while? But we are not checking the empty window. We are checking after adding a character. So the condition is: we have at least one character and distinct count > k. For k negative, even one distinct is > k (since 1 > -1). So we will always enter the while when we add a character. And then we remove that character, and then the window becomes empty (left>right). Then we update max_len with 0.But what about after we remove the character? The window becomes empty and then we are done with the while loop. Then we update max_len with 0. So it's okay.
However, note that when the window becomes empty (left>right) the length is 0. But in the update we do
right-left+1which becomes negative? Actually, if left>right, then right-left+1 is <=0. But we take max(0, ...) so it's 0.But wait, when left=1 and right=0, then right-left+1 = 0-1+1 = 0. So it's 0.
So the algorithm returns 0 for k negative.
But we might want to avoid the while loop when k is negative? Actually, the while loop condition will be true for any non-empty window because distinct>=1 and 1>k (if k<0). So we will always remove the added character immediately and then left becomes right+1. Then the window is empty. So we are doing O(n) operations but each right we do one addition and then one removal? Actually, in the worst case, for each right we do:
add s[right] then while condition: we remove s[left] (which is the same as s[right] because left was at right? Not necessarily. But in the case of k negative, after we add a character, we have distinct=1 (if the character is new) or more if it's already in? But note: we just added one character, so the distinct count is either 1 (if the character wasn't there) or still 1 (if it was already there and we increased count). Actually, if the character was already there, then distinct remains the same? Wait, we are adding a character that might already be in the window. So the distinct count might not increase.
Example: s="aa", k=-1.
right=0: char='a', char_count={'a':1} -> distinct=1 > -1 -> while: remove s[0] -> char_count['a']=0 -> remove key, left=1. then window [1,0] -> length 0. right=1: char='a', char_count={'a':1} (we start from left=1, so the window [1,1]? But we just added at index1 and then we remove s[1]? Let's see: We are at right=1, we add s[1]='a'. Now char_count={'a':1} (since we removed the previous one). Then while condition: distinct=1 > -1 -> remove s[1]? left is 1, so we remove s[1]? Then char_count['a']=0 -> remove key, left=2. Then window [2,1] -> length 0.
So we do two removals for two characters.
So it's O(n) but with a constant factor of 2 per character? Actually, each character is added once and removed once? But in this case, for each right, we add and then remove (if k negative). So it's O(n).
But we can avoid this by checking if k<0 at the beginning and returning 0.
Let's do:
if k < 0: return 0
This will make it clear and efficient.
However, the problem says integer k, and it might be negative. So we handle.
Alternatively, we can leave it as is because it still works. But let's be explicit.
I'll add:
if k < 0: return 0
Now, what about k=0? We already saw it returns 0.
But note: if k=0, then we cannot have any character. So we return 0.
Let's code accordingly.
However, note: the problem says "at most k distinct", so for k=0, we can have the empty substring, which has 0 distinct. But typically, we consider non-empty substrings? The problem says "substring", and by definition a substring can be empty? Usually, when we talk about substring length, we consider non-empty? But the empty substring has length 0 and 0 distinct. So if k>=0, then the empty substring is always valid. But we are looking for the longest, and if there's no non-empty, then 0 is correct.
But what if k=0 and s is non-empty? Then we cannot have any non-empty substring because any non-empty substring has at least 1 distinct. So the answer is 0.
So our algorithm returns 0 for k=0 and non-empty s? Let's test:
s="a", k=0: right=0: add 'a' -> distinct=1 >0 -> while: remove s[0] -> left=1, char_count empty. then update max_len = max(0, 0-1+1=0) -> 0. return 0.
So it's correct.
Now, let's code with the early return for k<0 and then the sliding window.
However, note that the problem says "at most k", so k can be 0 and we handle.
Let's code:
def longest_substring_with_at_most_k_distinct(s: str, k: int) -> int: if k < 0: return 0 left = 0 max_len = 0 char_count = {} for right in range(len(s)): char = s[right] char_count[char] = char_count.get(char, 0) + 1 while len(char_count) > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: del char_count[left_char] left += 1 max_len = max(max_len, right - left + 1) return max_len
Let's test with the example: s="eceba", k=2 -> expected 3.
right=0: 'e' -> char_count={'e':1} -> distinct=1 <=2 -> max_len=1 right=1: 'c' -> char_count={'e':1, 'c':1} -> distinct=2 <=2 -> max_len=2 right=2: 'e' -> char_count={'e':2, 'c':1} -> distinct=2 <=2 -> max_len=3 right=3: 'b' -> char_count={'e':2, 'c':1, 'b':1} -> distinct=3>2 -> while: left_char='e' -> char_count['e']=1 -> distinct still 3? Wait, we removed one 'e' but we still have 'e'? So distinct remains 3? Then we remove left_char again? Actually, after removing one 'e', we have char_count={'e':1, 'c':1, 'b':1} -> distinct=3. We continue while loop. Now left=1, remove s[1]='c': char_count['c']=0 -> remove 'c', left=2, char_count={'e':1, 'b':1} -> distinct=2, exit while. Then max_len = max(3, 3-2+1=2) -> 3. right=4: 'a' -> char_count={'e':1, 'b':1, 'a':1} -> distinct=3>2 -> while: left_char='e' (s[2]='e') -> char_count['e']=0 -> remove 'e', left=3, char_count={'b':1, 'a':1} -> distinct=2, exit while. Then max_len = max(3, 4-3+1=2) -> 3.
So returns 3.
But wait, the example "eceba" with k=2: the longest substring with at most 2 distinct is "ece" (length 3). But note that "eceb" has 3 distinct? e,c,b -> 3. So the algorithm found "ece" (from index0 to index2) and then at right=3 we had to shrink to [2,3] which is "eb" (2 distinct) and then at right=4 we had [3,4] "ba" (2 distinct). So the maximum was 3.
But what about "ec"? That's 2 distinct and length 2. So 3 is correct.
However, note that there's a substring "ceb"? That's 3 distinct. So not allowed.
So it's correct.
But wait, what about the substring "eb"? That's from index2 to index3, length 2.
So the algorithm is correct.
However, note that in the example, when we are at right=2, we have a window [0,2] which is "ece" and we update max_len to 3. Then at right=3, we add 'b' and then we shrink until we remove the 'c' (at left=1) and then the window becomes [2,3] which is "eb". Then we update max_len to 3 (since 3>2? No, we update with 2? Wait, right=3 and left=2, so length=2. Then we update max_len = max(3,2) -> 3.
So it's okay.
But what if we had a longer substring later? We update at every step.
Let's test with s="aabacbebebe", k=3 -> expected 7? Let me see:
According to known examples, the longest substring with at most 3 distinct in "aabacbebebe" is "cbebebe" (from index5 to index11) which has 3 distinct (c,b,e) and length 7.
Let's run the algorithm mentally:
We'll do step by step for the first few:
left=0, max_len=0 right=0: 'a' -> char_count={'a':1} -> distinct=1 -> max_len=1 right=1: 'a' -> char_count={'a':2} -> distinct=1 -> max_len=2 right=2: 'b' -> char_count={'a':2, 'b':1} -> distinct=2 -> max_len=3 right=3: 'a' -> char_count={'a':3, 'b':1} -> distinct=2 -> max_len=4 right=4: 'c' -> char_count={'a':3, 'b':1, 'c':1} -> distinct=3 -> max_len=5 right=5: 'b' -> char_count={'a':3, 'b':2, 'c':1} -> distinct=3 -> max_len=6 right=6: 'e' -> char_count={'a':3, 'b':2, 'c':1, 'e':1} -> distinct=4>3 -> while: remove s[0]='a' -> char_count['a']=2 -> distinct=4? Still 4 because a is still present? We have a,b,c,e -> 4. So we continue. left=1, remove s[1]='a' -> char_count['a']=1 -> distinct=4? Still 4. left=2, remove s[2]='b' -> char_count['b']=1 -> distinct=4? Still 4. left=3, remove s[3]='a' -> char_count['a']=0 -> remove 'a', now distinct=3 (b,c,e) -> exit while. Then window [4,6] -> "cbe", length=3, max_len remains 6. right=7: 'b' -> char_count={'b':2, 'c':1, 'e':1} -> distinct=3 -> max_len = max(6, 7-4+1=4) -> 6. right=8: 'e' -> char_count={'b':2, 'c':1, 'e':2} -> distinct=3 -> max_len = max(6, 8-4+1=5) -> 6. right=9: 'b' -> char_count={'b':3, 'c':1, 'e':2} -> distinct=3 -> max_len = max(6, 9-4+1=6) -> 6. right=10: 'e' -> char_count={'b':3, 'c':1, 'e':3} -> distinct=3 -> max_len = max(6, 10-4+1=7) -> 7. right=11: 'b' -> char_count={'b':4, 'c':1, 'e':3} -> distinct=3 -> max_len = max(7, 11-4+1=8) -> 8? Wait, but the substring from index4 to index11 is "cbebebeb"? That's 8 characters? Let's count: index4='c',5='b',6='e',7='b',8='e',9='b',10='e',11='b' -> that's 8 characters and distinct: c,b,e -> 3. So the longest is 8? But the example I thought was 7? Actually, the example string is "aabacbebebe", which has 11 characters (index0 to index10). Wait, let me check:
s = "aabacbebebe" indices: 0:a,1:a,2:b,3:a,4:c,5:b,6:e,7:b,8:e,9:b,10:e -> that's 11 characters? Wait, the string "aabacbebebe" has 11 characters? Let's count: a(2), b, a, c, b, e, b, e, b, e -> that's 10? Actually:
"aabacbebebe" -> a a b a c b e b e b e -> 11? Let's break: a (1) a (2) b (3) a (4) c (5) b (6) e (7) b (8) e (9) b (10) e (11) -> so index10 is the last? Actually, if we index from 0, then the last index is 10.
So in the step above, when right=10, we are at the last character? Then we have window [4,10] which is 7 characters? Because 10-4+1=7. But wait, we are at right=10 and left=4, so 7 characters: indices 4,5,6,7,8,9,10 -> that's 7. But then at right=11? There is no index11 because the string length is 11? Wait, the string length is 11? Actually, "aabacbebebe" has 11 characters? Let me count in Python:
len("aabacbebebe") 11
So indices 0 to 10.
In our mental run, we went to right=11? That was a mistake. We should stop at right=10.
Let's correct:
After right=10, we have:
right=10: char='e', char_count={'b':3, 'c':1, 'e':3} -> distinct=3 -> max_len = max(6, 10-4+1=7) -> 7.Then we are done. So the answer is 7.
But wait, the substring from index4 to index10 is "cbebebeb"? That's 7 characters: c(4),b(5),e(6),b(7),e(8),b(9),e(10) -> that's 7. But we have 'c' at index4 and then b,e,b,e,b,e -> that's 7.
But the example I thought was "cbebebe" (7) and we have 7. But wait, our window at the end is from index4 to index10, which includes 'c' at the beginning. But note that the substring "cbebebeb" has 3 distinct (c,b,e) and length 7? Actually, count: c,b,e,b,e,b,e -> that's 7? Wait, we have 7 characters: index4: c index5: b index6: e index7: b index8: e index9: b index10: e That's 7.
But the example I thought was "cbebebe" (from index5 to index10?) That would be 6? No, from index5 to index10 is 6 characters? Let me see:
index5: b index6: e index7: b index8: e index9: b index10: e -> that's 6.So the longest is from index4 to index10 (7) because it includes the 'c' at the beginning? But then we have 3 distinct: c,b,e. So it's valid.
But wait, when we added the 'c' at index4, we had to remove the first two 'a's and the 'b' at index2? Then we had window [4,6] which is "cbe". Then we kept adding b and e without adding a new distinct because we already had b and e? But note: at index7 we add 'b' (already there), index8 'e' (already there), index9 'b', index10 'e'. So we never exceed 3 distinct? But we have c,b,e -> 3. So the window [4,10] is valid.
So the algorithm returns 7, which is correct.
But note: in the step at right=10, we had left=4 and right=10, so length=7.
So the algorithm works.
However, note that the inner while loop in the step at right=6 (when we added 'e') removed until we got to left=4. Then at right=7,8,9,10 we didn't need to remove because we didn't exceed 3.
So the algorithm is correct.
Let's code accordingly.
But wait, what about the case when k is very large? Then we never enter the while loop and we just update max_len every time? That's O(n) and we update max_len at every step. That's acceptable.
So the code:
if k < 0: return 0
left = 0 max_len = 0 char_count = {} for right in range(len(s)): char = s[right] char_count[char] = char_count.get(char, 0) + 1 while len(char_count) > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: del char_count[left_char] left += 1 max_len = max(max_len, right - left + 1) return max_len
However, note that we are using
len(char_count)which is the number of distinct characters. This is O(1) in Python because dict maintains the number of keys? Actually, thelenfunction on a dictionary is O(1) because the dictionary stores the size.So the overall time complexity is O(n) and space O(k) (or O(min(n, k)) because the dictionary size is at most k+1? Actually, we remove when we shrink, so the dictionary size is at most k+1? Wait, we only enter the while when we have >k, and we remove until we have <=k. So the dictionary size never exceeds k+1? Actually, we add one and then if it becomes k+1, we remove until it becomes k. So the maximum size is k+1 (for a moment) and then we reduce to k. So the space is O(k).
But note: k can be large, up to the number of distinct characters in the string. But in the worst case, k is the total distinct, then we never remove and the dictionary grows to the number of distinct in the entire string. So space is O(min(n, |Σ|)) where Σ is the alphabet.
But we can say O(k) because we are only storing at most k+1 keys at any time? Actually, when we add a new key and the dictionary size becomes k+1, then we remove until we have k. So the dictionary size is at most k+1. But wait, what if we have multiple of the same character? The dictionary size is the number of distinct, so it's at most k+1.
So space is O(k).
However, note that k can be up to n (the length of the string) and then the dictionary size is at most n? But in the worst case, the string has n distinct characters and k=n, then we never remove and the dictionary size is n. So it's O(min(n, k))? Actually, if k>= number of distinct in the entire string, then the dictionary will hold all distinct characters. So it's O(|Σ|) but bounded by n.
But we can say O(k) because we are only storing up to k+1 distinct? Wait, if k is larger than the number of distinct in the entire string, then we store all distinct, which is at most n. So it's O(min(n, k))? Actually, if k is very large, we store all distinct, which is at most the number of distinct in s, which is <= n. So it's O(min(n, k))? But note: k can be arbitrarily large? Then we store all distinct, which is at most the size of the alphabet (if we assume a fixed alphabet, then O(1)). But in the worst case, the string can have all distinct characters, so n distinct. So O(n) in the worst case.
But we can say the space complexity is O(min(n, k))? Actually, the dictionary size is at most min(total distinct in s, k+1). But total distinct in s is at most n. So it's O(min(n, k)).
However, note that we are only storing the counts for the current window, and the window has at most k+1 distinct. So the dictionary size is at most k+1. But if k is larger than the total distinct in s, then we store all distinct, which is less than k+1? Actually, if k is larger than the total distinct, then we store all distinct (which is <= k). So the dictionary size is at most min(total distinct, k+1). But total distinct is at most n. So we can say O(min(n, k)).
But in the worst case, when k is very large, we store all distinct of the entire string, which is at most n. So O(n).
But note: the problem does not specify the alphabet. So we assume the worst case.
We can state: time O(n), space O(min(n, k)).
But in the code, we are only storing up to k+1 distinct? Actually, we remove when we exceed k, so we never have more than k+1 distinct in the dictionary. Wait, we add one and then if we exceed k, we remove until we have k. So the maximum size of the dictionary is k+1? Let's see:
Suppose we have k=2. We add a new character that makes the distinct count 3. Then we remove until we have 2. So the dictionary size during the while loop might be 3 for a moment, but then we remove and it becomes 2. So the maximum size is k+1.
But what if we add a character that is already in the dictionary? Then the distinct count doesn't increase. So we never exceed k? Then the dictionary size remains at most k.
So the dictionary size never exceeds k+1. Therefore, the space is O(k).
But wait, what if k is 0? Then we never store any character? Actually, we store and then remove immediately. So the dictionary is empty most of the time. So O(1).
So we can say O(k) because we store at most k+1 distinct characters.
However, note that k can be larger than the number of distinct in the entire string. Then we store all distinct, which is less than k+1? But then the dictionary size is the total distinct, which is at most n. So it's O(min(n, k)).
But note: if k is larger than the total distinct, then we never enter the while loop and the dictionary grows to the total distinct. So the space is the total distinct in s, which is at most n. So it's O(min(n, k))? Actually, if k is larger than the total distinct, then we store all distinct (which is <= k). So it's O(total distinct) which is <= n.
But we can also say O(k) because we are storing at most k+1, but if k is huge, then we store all distinct (which is less than k+1). So it's O(min(n, k)).
I think it's safe to say O(k) because we are storing at most k+1 distinct, and k+1 is the bound. But if k is larger than n, then we store at most n distinct. So it's O(min(n, k)).
However, in the worst case, k can be very large (like 10^9) and n is 10^5, then we store at most n distinct. So it's O(n). So we can say O(min(n, k)).
But note: the problem says integer k, so k can be very large. So we should say O(min(n, k)).
Alternatively, we can say O(k) but note that k can be much larger than n, then we store at most n distinct. So it's O(n) in that case.
Let's state: time O(n), space O(min(n, k)).
But wait, the dictionary size is at most the number of distinct in the current window, which is at most k+1. So if k is less than the total distinct, then we store at most k+1. If k is larger, then we store at most the total distinct in the string (which is <= n). So it's O(min(n, k)).
So we'll go with that.
Now, let's write the function with comments.
However, note that the problem says "write a function that solves this problem, and explain your algorithm."
We have explained.
Let's write the code accordingly. This is a classic sliding window problem. We maintain a window
[left, right]that always contains at mostkdistinct characters. As we expand the window to the right, we track character counts in a hash map. If the number of distinct characters exceedsk, we shrink the window from the left until the condition is satisfied again. The maximum window size encountered during this process is our answer.Algorithm Walkthrough:
- Edge case: If
k < 0, return0(no valid substring exists). - Initialize:
left = 0(left boundary of window)max_len = 0(result)char_count = {}(hash map: character → frequency in current window)
- Expand right pointer from
0tolen(s)-1:- Add
s[right]tochar_count. - While distinct characters (
len(char_count)) >k:- Decrease count of
s[left]inchar_count. - If count drops to
0, remove the key fromchar_count. - Move
leftrightwards.
- Decrease count of
- Now window
[left, right]has ≤kdistinct characters → updatemax_len.
- Add
- Return
max_len.
Complexity:
- Time:
O(n)— each character is processed at most twice (once byright, once byleft). - Space:
O(min(n, k))— hash map stores at mostk+1distinct characters (or all distinct ifkis large).
Code:
def length_of_longest_substring_k_distinct(s: str, k: int) -> int: if k < 0: return 0 left = 0 max_len = 0 char_count = {} for right in range(len(s)): char = s[right] char_count[char] = char_count.get(char, 0) + 1 # Shrink window until we have at most k distinct characters while len(char_count) > k: left_char = s[left] char_count[left_char] -= 1 if char_count[left_char] == 0: del char_count[left_char] left += 1 # Update answer with current valid window size max_len = max(max_len, right - left + 1) return max_lenExample:
s = "eceba" k = 2 print(length_of_longest_substring_k_distinct(s, k)) # Output: 3 ("ece")Explanation of example:
- Window
[0, 0]→"e"→ 1 distinct →max_len=1 - Window
[0, 1]→"ec"→ 2 distinct →max_len=2 - Window
[0, 2]→"ece"→ 2 distinct →max_len=3 - Window
[0, 3]→"eceb"→ 3 distinct → shrink to[2, 3]("eb") →max_lenunchanged. - Window
[2, 4]→"ebba"? Actually after processing'a'at index 4, window becomes[3,4]("ba") →max_lenremains3.
Thus, the longest valid substring is
"ece"with length3.