首页 > itarticle > Trivia leetcode-340. Longest Substring with At Most K Distinct Characters

Trivia leetcode-340. Longest Substring with At Most K Distinct Characters

admin 11月 12, 2020 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.

Show Company Tags
Show Tags
Show Similar Problems
原题地址

利用hash table统计substring里的字符，类似的以char为key的题都可以用数组来做，会快一些。

int (string s, int k) {
    unordered_map<char, int> hash;
    int res = 0;
    int p_1 = 0;
    for (int p_2 = 0; p_2 < s.size(); p_2++) {
        hash[s[p_2]]++;
        while (hash.size() > k) {
            if (--hash[s[p_1]] == 0) {
                hash.erase(s[p_1]);
            }
            p_1++;
        }
        res = max(res, p_2 - p_1 + 1);
    }
    return res;
}