Longest Substring with At Most K Distinct Characters

Question

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

Example

given s = "abcba" and k = 2
return "bcb"

Solution

We use sliding window to solve it and need to maintain the num to keep tracking of different characters during the process.

Code

// time:O(n) space:O(128) ~ O(1)
public static String getStringNoMoreKDistinct(String s, int k) {
        if (s == null || s.length() == 0) return "";
        int[] counter = new int[128];
        int end = 0;
        int start = 0;
        int num = 0;
        int max = 0;
        String res = "";
        while (end < s.length()) {
            if (counter[s.charAt(end)]++ == 0) num++;
            while (num > k) {
                counter[s.charAt(start)]--;
                if (counter[s.charAt(start)] == 0) num--;
                start++;
            }
            end++;
            if (end - start > max) {
                max = end - start;
                res = s.substring(start, end);
            }
        }
        return res;
    }