【HARD】Longest Substring with At Most K Distinct Characters

发布于: 2019-01-14 23:25
阅读: 74
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

分析过程

  • 输入:一个字符串
  • 输出:最长含有 k 个不同字符的字符串长度
  • 思路:使用哈希表存储出现的次数。只含有 k 个字符就意味着哈希表最长只能是 k,扫描时保证哈希表长度是 k 即可。

解决方法

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int len = (int)s.size();
        if (len == 0) {
            return 0;
        }
        
        int result = 0;
        map<char, int> m;
        int begin = 0;
        
        for (int i = 0; i < len; i++) {
            char c = s[i];
            // 当前字母出现次数+1
            m[c]++;
            // 保证哈希表长度是2
            // 如果哈希表长度大于2,则窗口的开始端就要向右移动
            while (m.size() > k) {
                // 起始端向右移动,如果出现次数变为0就直接清除掉
                char b = s[begin];
                m[b]--;
                if (m[b] <= 0) {
                    m.erase(b);
                }
                begin++;
            }
            // 哈希表长度是2的情况下取最大长度
            result = max(result, i - begin + 1);
        }
        
        return result;
    }
};

Thanks for reading.

All the best wishes for you! 💕