Longest Substring with At Most K Distinct Characters

题目(LeetCode #340)

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

题解

使用滑动窗口遍历字符串，统计窗口内不同字符的数量。

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;

        char[] chArr = s.toCharArray();
        int[] freqArr = new int[128]; // 没有限定是小写英文字母
        int n = s.length();
        int l = 0, r = 0;
        int count = 0, result = 0;

        while (r < n) {
            int cIdx = chArr[r] - '!';
            freqArr[cIdx]++;
            if (freqArr[cIdx] == 1) count++;

            while (count > k) {
                int tIdx = chArr[l++] - '!';
                freqArr[tIdx]--;
                if (freqArr[tIdx] == 0) count--;
            }

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

        return result;
    }
}