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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

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;     } }