LeetCode 340 Longest Substring with At Most K Distinct Characters

LeetCode

<div>

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:

<pre>Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3.</pre>

Example 2:

<pre>Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2. </pre>

Constraints:

• 1 <= s.length <= 5 * 10<sup>4</sup>
• 0 <= k <= 50

</div>

题目大意：

求最长子串，它含有最多k种字符

解题思路：

同向双指针，属于最长串类型

解题步骤：

N/A

注意事项：

1. while条件中，反计算char_to_count，还要pop key

Python代码：

def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
	char_to_count, left, max_len = collections.defaultdict(int), 0, 0
	for i, char in enumerate(s):
		char_to_count[char] += 1
		while len(char_to_count) > k:
			char_to_count[s[left]] -= 1
			if char_to_count[s[left]] == 0:
				char_to_count.pop(s[left])
			left += 1
		max_len = max(max_len, i - left + 1)
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(k)