340. Longest Substring with At Most K Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/description/

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.

Thoughts

包含最多K个不同字符的最长子数组的长度。返回最长的连续子串的长度=>动态滑动窗口。内循环压缩滑动窗口(++l)，使得滑动窗口在每次循环后满足题目要求，即最多K个不同的字符。用dict记录窗口各char出现的频率并统计独特元素个数，如果窗口内独特元素超过了k，则开始压缩窗口。

Code

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int res = 0;
        unordered_map<char, int> freqs;
        for (int l = 0, r = 0, cnt = 0; r < s.length(); ++r) {
            const auto rk = s[r];
            if (freqs[rk] == 0) ++cnt;
            ++freqs[rk];
            while (cnt > k) {
                const auto lk = s[l];
                --freqs[lk];
                ++l;
                if (freqs[lk] == 0) --cnt;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>(); 

        int l = 0, r = 0, res = 0;
        while (r < s.length()) {
            char c = s.charAt(r);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            int count = 0;
            for (Character ch : freq.keySet()) {
                if (freq.get(ch) > 0) {
                    count++;
                }
            }

            if (count > k) {
                freq.put(s.charAt(l), freq.get(s.charAt(l)) - 1);
                l++;
            }

            res = Math.max(res, r - l + 1);
            r++;
        }

        return res;
    }
}

Analysis

时间复杂度O(N).