
Given a string S, find the length of the longest substring T that contains at most k distinct characters.
Example
No.1
Input: S = “eceba” and k = 3
Output: 4
Explanation: T = “eceb”
No.2
Input: S = “WORLD” and k = 4
Output: 4
Explanation: T = “WORL” or “ORLD”
Challenge
O(n) time
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
public int (String s, int k) { int result = 0; int[] count = new int[128]; int num = 0; int start = 0; int end = 0;
while (end < s.length()) { int idxEnd = s.charAt(end) - '0';
if (count[idxEnd] == 0) num++;
count[idxEnd]++; end++;
while (num > k) { int idxStart = s.charAt(start) - '0'; count[idxStart]--;
if (count[idxStart] == 0) num--;
start++; }
result = Math.max(result, end - start); }
return result; }
|
近期评论