Lintcode 386. Longest Substring with At Most K Distinct Characters

Description

中文English

Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Have you met this question in a real interview?  

Example

Example 1:

Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"

Example 2:

Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"

Challenge

O(n) time

Code (Java):

public class Solution {
    /**
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }

        int[] counts = new int[256];
        int left = 0;
        int maxLen = 0;
        int numDistinct = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            counts[c]++;

            if (counts[c] == 1) {
                numDistinct++;
            }

            while (numDistinct > k) {
                counts[s.charAt(left)]--;
                if (counts[s.charAt(left)] == 0) {
                    numDistinct--;
                }
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}