[LeetCode] 340. Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:
Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.

Example 2:
Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.

Constraints:
1 <= s.length <= 5 * 104
0 <= k <= 50

至多包含K个不同字符的最长子串。

思路

这个题跟 159 题一模一样，无非是把最多两个字母改成了最多 K 个字母。还是 sliding window 的思路做。不熟悉的话可以先做 159 题。

复杂度

时间O(n)
空间O(1) - 只是一个256位长度的数组

代码

Java实现

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] map = new int[256];
        int start = 0;
        int end = 0;
        int res = Integer.MIN_VALUE;
        int counter = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map[c1] == 0) {
                counter++;
            }
            map[c1]++;
            end++;
            while (counter > k) {
                char c2 = s.charAt(start);
                map[c2]--;
                if (map[c2] == 0) {
                    counter--;
                }
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var lengthOfLongestSubstringKDistinct = function(s, k) {
    // corner case
    if (s == null || s.length == 0) {
        return 0;
    }

    // normal case
    let start = 0;
    let end = 0;
    let maxLen = -Infinity;
    let counter = 0;
    let map = {};
    while (end < s.length) {
        let c1 = s.charAt(end);
        if (map[c1] == null || map[c1] <= 0) {
            counter++;
        }
        map[c1] = map[c1] + 1 || 1;
        end++;
        while (counter > k) {
            let c2 = s.charAt(start);
            if (map[c2] == 1) {
                counter--;
            }
            map[c2]--;
            start++;
        }
        maxLen = Math.max(maxLen, end - start);
    }
    return maxLen;
};