[leetcode]340. Longest Substring with At Most K Distinct Characters至多包含K种字符的最长子串...

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.

题意：

给定字符串，求至多包含K种字符的最长子串

 

思路：

跟[leetcode]159. Longest Substring with At Most Two Distinct Characters至多包含两种字符的最长子串思路大体相同

j j S= “e c e b a” and k = 2, return 3 for "e c e" i e-0 map.size <=2 move i i c-1 map.size <=2 move i i e-2(update) map.size <=2 move i --------- b-3 map.size >2 get the length then move j i

 

代码：

1 class Solution { 2 public int lengthOfLongestSubstringKDistinct(String s, int k) { 3 //corner 4 if(s.length() < k ) return s.length(); 5 // general 6 HashMap<Character, Integer> map = new HashMap<>(); 7 int j = 0; 8 int result = 0; 9 for(int i = 0; i < s.length(); ){ 10 char c = s.charAt(i); 11 if(map.size() <= k){ 12 map.put(c, i); 13 i++; 14 } 15 if(map.size() > k){ 16 int leftMost = s.length(); 17 for(int n : map.values()){ 18 leftMost = Math.min(n, leftMost); 19 } 20 21 map.remove(s.charAt(leftMost)); 22 j = leftMost + 1; 23 } 24 result = Math.max(i - j , result); 25 26 } 27 return result; 28 29 } 30 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/9201947.html

相关资源：数据结构—成绩单生成器