洛谷p1833解决思路

洛谷 P1833 题目描述：

给定一个字符串 $s$ 和一个正整数 $k$，求出 $s$ 中最长的子串，使得该子串中不同字符的个数不超过 $k$。

解决思路：

本题可以使用滑动窗口来解决。具体思路如下：

1. 定义两个指针 $left$ 和 $right$，分别表示滑动窗口的左右边界。

2. 将 $left$ 和 $right$ 都初始化为 0。

3. 定义一个 HashMap，用于存储当前窗口内每种字符出现的次数。

4. 定义一个变量 $max_len$，用于记录最长子串的长度。

5. 当 $right < len(s)$ 时，执行以下操作：

a. 将 $s[right]$ 加入到 HashMap 中，如果不存在，则将其出现次数初始化为 1，否则将其出现次数加 1。

b. 如果 HashMap 中不同字符的个数大于 $k$，则需要将 $left$ 向右移动，并将对应字符的出现次数减 1，直到 HashMap 中不同字符的个数小于等于 $k$。

c. 更新 $max_len$，即 $max_len = max(max_len, right - left + 1)$。

d. 将 $right$ 向右移动一位，继续执行步骤 5。

6. 最后返回 $max_len$ 即可。

代码实现：

def max_len_substring(s, k):
    left, right = 0, 0
    char_count = {}
    max_len = 0
    while right < len(s):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
        right += 1
    return max_len

时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。

空间复杂度：$O(k)$，其中 $k$ 是不同字符的个数。