leetcode：340. 至多包含 K 个不同字符的最长子串（会员题）
相同题目：LintCode [中等] 386 · 最多有k个不同字符的最长子字符串

题目

给定字符串 S，找到最多有 k 个不同字符的最长子串 T。

示例：

  1. 输入: S = "eceba" 并且 k = 3
  2. 输出: 4
  3. 解释: T = "eceb"
输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"

解答 & 代码

滑动窗口

class Solution {
public:
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
        // 哈希表，存储当前窗口中的字符及出现次数
        unordered_map<char, int> window;
        int len = s.size();
        int result = 0;
        int left = 0;
        int right = 0;
        while(right < len)
        {
            char ch = s[right];
            ++right;

            ++window[ch];
            if(window.size() == k)
                result = max(right - left, result);

            // 如果窗口中的字符种数大于 k，则收缩左边界，直到窗口中的字符种数小于等于 k
            while(window.size() > k)
            {
                char leftCh = s[left];
                ++left;
                --window[leftCh];
                if(window[leftCh] == 0)
                    window.erase(leftCh);
            }
        }
        // 注意别遗忘这句！因为可能窗口种字符种数没超过 k，右边界就越界了
        result = max(right - left, result);
        return result;
    }
};

复杂度分析：设字符串长为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(K)：

执行结果：

执行结果：通过

执行用时：325 ms, 在所有 C++ 提交中击败了 36.40% 的用户
内存消耗：4.15 MB, 在所有 C++ 提交中击败了 36.40% 的用户