Longest Substring with At Most K Distinct Characters

Problem:

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.

3/1/2018 update:
Solution follow template:

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0) 
            return 0;
        int l = 0, r = 0, counter = 0, res = 0;
        int[] map = new int[256];
        while (r < s.length()) {
            if (map[s.charAt(r++)]++ == 0) counter++;
            // not satisfy
            while (counter > k) {
                // move left pointer
                if (map[s.charAt(l++)]-- == 1) counter--;
            }
            // update result
            res = Math.max(res, r - l);
        }
        return res;
    }
}

Analysis:

The key point of this sort of problem is to maintain a sliding window. i and j, j keeps moving forward. Once the window doesn't satisfy the condition then move i so that the new window satisfy the condition, then update result. 

Use a int[256] (map) array to store count of each character. The total number of distinct characters is easy to count. Once that count is larger then k, window needs to be updated. Take "eceba" as an example, when j == 3, sliding window violates the condition, count is 3. So we just need to move i to reduce the count by 1. Remove letter one by one as i increase, when map[s[i]] == 0, we know that i++ reach the new sliding window start point.

Solution:

 public class Solution {  
   public int lengthOfLongestSubstringKDistinct(String s, int k) {  
     int[] map = new int[256];  
     int count = 0;  
     int i = 0, res = 0;  
     for (int j = 0; j < s.length(); j++) {  
       if ((map[s.charAt(j)]++) == 0) count++;  
       if (count > k) {  
         // reduce one occurance  
         while (--map[s.charAt(i++)] > 0);  
         count--;  
       }  
       res = Math.max(res, j - i + 1);  
     }  
     return res;  
   }  
 }