【HARD】Longest Substring with At Most K Distinct Characters

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

问题

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

分析过程

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

解决方法

using namespace std;

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

int main() {
    const char *c = "eceba";
    cout << longestSubstring(c, 2) << endl;
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕