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

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

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

时间O(n)

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

Java实现

 1 class Solution {
 2     public int lengthOfLongestSubstringKDistinct(String s, int k) {
 3         // corner case
 4         if (s == null || s.length() == 0) {
 5             return 0;
 6         }
 7 
 8         // normal case
 9         int[] map = new int[256];
10         int start = 0;
11         int end = 0;
12         int maxLen = Integer.MIN_VALUE;
13         int counter = 0;
14         while (end < s.length()) {
15             char c1 = s.charAt(end);
16             if (map[c1] == 0) {
17                 counter++;
18             }
19             map[c1]++;
20             end++;
21             while (counter > k) {
22                 char c2 = s.charAt(start);
23                 if (map[c2] == 1) {
24                     counter--;
25                 }
26                 map[c2]--;
27                 start++;
28             }
29             maxLen = Math.max(maxLen, end - start);
30         }
31         return maxLen;
32     }
33 }

JavaScript实现

 1 /**
 2  * @param {string} s
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var lengthOfLongestSubstringKDistinct = function(s, k) {
 7     // corner case
 8     if (s == null || s.length == 0) {
 9         return 0;
10     }
11 
12     // normal case
13     let start = 0;
14     let end = 0;
15     let maxLen = -Infinity;
16     let counter = 0;
17     let map = {};
18     while (end < s.length) {
19         let c1 = s.charAt(end);
20         if (map[c1] == null || map[c1] <= 0) {
21             counter++;
22         }
23         map[c1] = map[c1] + 1 || 1;
24         end++;
25         while (counter > k) {
26             let c2 = s.charAt(start);
27             if (map[c2] == 1) {
28                 counter--;
29             }
30             map[c2]--;
31             start++;
32         }
33         maxLen = Math.max(maxLen, end - start);
34     }
35     return maxLen;
36 };

sliding window相关题目

LeetCode 题目总结