/**
 * Given a string, find the length of the longest substring T that contains at most k distinct characters. 
 * For example, given s = "ecceba" and k = 2,
 * T is "ece" which has a length of 3 and 2 distinct characters.
 */
public class Solution {
  public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() == 0 || (s.length() == 1 && k == 1)) return s.length();
    if (s.length() == 1 && k > 1) return 0;

    int i = 0; 
    int j = 1;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int distinct = s.charAt(i) == s.charAt(j) ? 1 : 2;
    int maxLength = 0;
    map.put(s.charAt(i), 1);
    map.put(s.charAt(j), distinct);

    while (i < j && j < s.length() - 1) {
      char next = s.charAt(j + 1);
      // The number of distinct character is equal to K so we must remove the first distinct characters from the front.
      if (distinct > k) {
        char start = s.charAt(i);
        while (i < s.length() && start == s.charAt(i)) { 
          i ++;
          map.put(start, Math.max(0, map.containsKey(start) ? map.get(start) - 1 : 0));
        }

        distinct --;
      } else {
        maxLength = Math.max(maxLength, j - i + 1);
      }

      int count = map.containsKey(next) ? map.get(next) : 0;
      distinct = count != 0 ? distinct : distinct + 1; 
      map.put(next, count + 1);
      j ++;
    }

    return distinct > k ? maxLength : Math.max(maxLength, j - i + 1);
  } 
}

@@ -1,8 +1,28 @@
+import java.util.*;%0A
 /**%0A * G
@@ -273,16 +273,23 @@
  public 
+static 
 int leng
@@ -364,17 +364,16 @@
 == 0 %7C%7C 
-(
 s.length
@@ -383,19 +383,8 @@
 == 1
- && k == 1)
 ) re
@@ -412,32 +412,14 @@
 if (
-s.length() == 1 && k %3E 1
+k == 0
 ) re
@@ -455,17 +455,17 @@
 int j = 
-1
+0
 ;%0A    Ha
@@ -554,42 +554,9 @@
 t = 
-s.charAt(i) == s.charAt(j) ? 1 : 2
+0
 ;%0A  
@@ -576,28 +576,64 @@
 th = 0;%0A
+%0A
     
-map.put(
+while (j %3C s.length()) %7B%0A      char next = 
 s.charAt
@@ -637,129 +637,161 @@
 rAt(
-i), 1
+j
 );%0A    
-map.put(s.charAt(j), distinct);%0A%0A    while (i %3C j && j %3C s.length() - 1) %7B
+  int count = map.get(next) != null && map.get(next) %3E 0 ? map.get(next) : 0;%0A      map.put(next, count + 1);
 %0A      
-char next = s.charAt(j + 1);
+if (count == 0) distinct ++;%0A
 %0A   
@@ -869,13 +869,9 @@
 the 
-first
+a
  dis
@@ -889,24 +889,34 @@
 cter
-s from the front
+ and all of its occurences
 .%0A  
@@ -977,166 +977,231 @@
 i);%0A
-        while (i %3C s.length() && start == s.charAt(i)) %7B %0A          i ++;%0A          map.put(start, Math.max(0, map.containsKey(start) ? map.get(start
+%0A        // Keep moving the beginning pointer until a character frequency is 0%0A        while (i %3C j && map.get(s.charAt(i)) != null && map.get(s.charAt(i)) - 1 %3E 0) %7B%0A          map.put(s.charAt(i), map.get(s.charAt(i++
 ) - 1
- : 0
 ));%0A
@@ -1223,164 +1223,85 @@
     
-distinct --;%0A      %7D else %7B%0A        maxLength = Math.max(maxLength, j - i + 1);%0A      %7D%0A%0A      int count = map.containsKey(next) ? map.get(next) :
+// Remove the last character.%0A        map.put(s.charAt((i++) - 1),
  0
+)
 ;%0A      
 dist
@@ -1300,177 +1300,121 @@
     
-distinct = count != 0 ? distinct : distinct + 1; %0A      map.put(next, count + 1);%0A      j ++;%0A    %7D%0A%0A    return distinct %3E k ? maxLength : Math.max(maxLength, j - i + 1)
+  distinct --;%0A      %7D%0A%0A      maxLength = Math.max(maxLength, j - i + 1);%0A      j ++;%0A    %7D%0A%0A    return maxLength
 ;%0A  

Update 340