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.
A:
就是用 HashMap 开计算 number of different characters.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: int lengthOfLongestSubstringKDistinct(string s, int k) { unordered_map<char, int> M; int start = 0; int res = 0; for(int end = 0;end<s.length();end++){ char ch = s[end]; M[ch]++; while(M.size() > k){ char delChar = s[start++]; M[delChar]--; if(M[delChar] ==0){ M.erase(delChar); } } res = max(res, end-start+1); } return res; } }; |
No comments:
Post a Comment