340. Longest Substring with At Most K Distinct Characters

O(n) time O(26) space
是159. Longest Substring with At Most Two Distinct Characters 的follow-up

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> m;
        int res = 0;
        int n = s.length();
        for (int l = 0, r = 0; r < n; ++r) {
            ++m[s[r]];
            while (m.size() > k) { // 注意k有可能为0
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
            res = max(res, r + 1 - l);
        }
        return res;
    }
};

lee的做法

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if (k == 0) return 0;
        unordered_map<char, int> m;
        int res = 0, l = 0, r = 0;
        int n = s.length();
        for (; r < n; ++r) {
            ++m[s[r]];
            if (m.size() > k) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
        }
        return r - l;
    }
};