Longest Substring with At Most K Distinct Characters
Home | Coding Interviews | Arrays and Strings | Longest Substring with At Most K Distinct Characters
Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.
public class Solution {
public int lengthOfLongestSubstringKDistinct(String S, int K) {
int[] charCount = new int[256];
char[] chS = S.toCharArray();
int distinctNum = 0, leftIndex = 0, maxLen = 0;
for (int rightIndex = 0; rightIndex < chS.length; rightIndex++) {
if (charCount[chS[rightIndex]]++ == 0) distinctNum++;
if (distinctNum > K) {
while (--charCount[chS[leftIndex++]] > 0);
distinctNum--;
}
maxLen = Math.max(maxLen, rightIndex - leftIndex + 1);
}
return maxLen;
}
}
Posted by Jamie Meyer 13 days ago