题解65 | #至多包含K种字符的子串#

滑动窗口思想：通常用于解决连续子序列问题。该算法通过维护一个固定大小的窗口，将问题转化为对窗口内元素的处理，从而实现高效的计算。具体而言，滑动窗口算法通过移动窗口的起始位置和结束位置，不断更新窗口内的元素，以得到问题的解。

#include <algorithm>
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int longestSubstring(string s, int k) {
        // write code here
        int res = 0;
        int n = s.size();
        unordered_map<char, int> ump;
        int left = 0, right = 0,count = 0;//滑动窗口左右指针
        
        while (right < n) {
            if (ump[s[right]] == 0) {
                count++;
            }
            ump[s[right]]++;
            right++;

            while (count > k) {
                if (ump[s[left]] == 1) {
                    count--;
                }
                ump[s[left]]--;
                left++;
            }

            res = max(res, right - left);
        }
        return res;
    }
};

算法基本思想：

使用滑动窗口的方法，遍历字符串s，用一个unordered_map记录每个字符出现的次数，同时维护一个滑动窗口，当窗口内不同字符的数量大于k时，左指针右移，直到满足条件为止，同时更新最大长度。

时间复杂度：

O(n)，其中n为字符串s的长度，需要遍历整个字符串s。

空间复杂度：

O(1)，使用了固定大小的unordered_map来记录字符出现的次数，不随输入规模增大而增大。