Longest Substring With At Most K Distinct Characters

Longest Substring With At Most K Distinct Characters string

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.

Longest Substring With At Most K Distinct Characters Solution

public class LongestSubstringWithAtMostKDistinctCharacters {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {

    int[] count = new int[256];     // there are 256 ASCII characters in the world

    int i = 0;  // i will be behind j
    int num = 0;
    int res = 0;

    for (int j = 0; j < s.length(); j++) {
        if (count[s.charAt(j)] == 0) {    // if count[s.charAt(j)] == 0, we know that it is a distinct character
            num++;
        }

        count[s.charAt(j)]++;

        while (num > k && i < s.length()) {     // sliding window
            count[s.charAt(i)]--;

            if (count[s.charAt(i)] == 0){
                num--;
            }

            i++;
        }

        res = Math.max(res, j - i + 1);
    }

    return res;
    }
}
Last modified October 4, 2020