Description
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3.
Example 2:
Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2.
Constraints:
1 <= s.length <= 5 * 1040 <= k <= 50
Explanation
Have a hashmap to record the number of the occurrence of the visited characters. Pointer j moves faster, pointer i moves slower. Keep moving the right pointer as long as the number of visited distinct characters is no greater than k. Move the slower pointer to the right and reduce the number of characters the slow pointer points in hashmap.
Python Solution
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
if k == 0:
return 0
result = 0
counter = {}
j = 0
for i in range(len(s)):
while j < len(s) and (len(counter) < k or (len(counter) == k and s[j] in counter)):
counter[s[j]] = counter.get(s[j], 0) + 1
j += 1
if len(counter) <= k:
result = max(result, j - i)
counter[s[i]] -= 1
if counter[s[i]] == 0:
del counter[s[i]]
return result
- Time Complexity: O(N).
- Space Complexity: O(N).