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.

?

Analyses: Map each character in the string into a index?in an array times, size of that array is from ASCII size. During the process of scanning, update the frequencies of each character. Have a variable count to label how many different characters occur. Whenever the count exceeds k, we know that shorten our range: Let the left pointer move right until the frequency of the character pointed by left is 1.?

1 public class Solution { 2 public int lengthOfLongestSubstringKDistinct(String s, int k) { 3 int result = 0, left = 0, n = s.length(), count = 0; 4 int[] times = new int[256]; // map char in s to a index 5 for (int right = 0; right < n; right++) { 6 if (times[s.charAt(right)]++ == 0) count++; 7 8 if (count > k) { 9 while (--times[s.charAt(left++)] > 0); 10 count--; 11 } 12 13 result = Math.max(result, right - left + 1); 14 } 15 return result; 16 } 17 }

?

轉載于:https://www.cnblogs.com/amazingzoe/p/6768022.html

總結

以上是生活随笔為你收集整理的Longest Substring With At Most K Distinct Characters的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。