至多包含k个不同字符的最长子串

02 Nov 2024 in Algorithm Pageviews

滑动窗口

给你一个字符串 s 和一个整数 k ，请你找出至多 包含 k 个不同字符的最长子串，并返回该子串的长度

示例1：

输入：s = “eceba”, k = 2

输出：3

解释：满足题目要求的子串是”ece”，长度为3

示例2：

输入：s = “aa”, k = 1

输出：2

解释: 满足题目要求的子串是“aa”，长度为2

提示：

1 <= s.size() <= 5 * 10⁵

0 <= k <= 50

代码实现如下:

class Solution {
public:
    int LengthOfLongestSubstringKDistinct(string s, int k)
    {
        int len = INI_MIN;
        map<char, int> mp;
        for (auto l = 0, r = 0; r < s.size(); r++) {
            mp[s[r]]++;
            while (mp.size() > k) {
                mp[s[l]]--;
                if (mp[s[l]] == 0) {
                    mp.erase(s[l]);
                }
                l++;
            }
            len = max(len, r - l + 1);
        }
        return len;
    }
};