Longest Substring With At Most K Distinct Characters
Description
Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: The longest substring with at most 2 distinct characters is "ece" (length 3). It contains only 'e' and 'c'.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The entire string "aa" has only 1 distinct character, which is <= 1.
Example 3:
Input: s = "aabbcc", k = 2
Output: 4
Explanation: The longest substring with at most 2 distinct characters is "aabb" or "bbcc" (both length 4).
Constraints
1 <= s.length <= 5 * 10^40 <= k <= 50s consists of lowercase English letters
Complexity
Show Complexity
- Time:
O(n) - Space:
O(k)
Hints
Show Hints
- Pattern
- Sliding window with hash map
- Approach
- Expand right pointer, when distinct chars > k, shrink left pointer until valid. Track max length.
- Complexity
- Maintain a window with at most k distinct chars using a frequency map
Solutions
Show PY Solution
def solution(s: str, k: int) -> int:
m = {}
left = 0
result = 0
for right in range(len(s)):
a = s[right]
if a not in m:
m[a] = 0
m[a] += 1
while len(m) > k:
m[s[left]] -= 1
if m[s[left]] == 0:
del m[s[left]]
left += 1
result = max(result, sum(m.values()))
return result