Skip to Content

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