Subarrays with K Different Integers.java

  public int lengthOfLongestSubStringAtMostKDistinct(String s, int k) {
    int n = s.length();
    int[] count = new int[256];
    int i = 0, numDistinct = 0, ans = 0;

    for (int j = 1; j < s.length(); j++) {
      if (count[s.charAt(j)] == 0) {
        numDistinct++;
      }
      count[s.charAt(j)]++;
      while (numDistinct > k) {
        count[s.charAt(i)]--;
        if (count[s.charAt(i)] == 0) {
          numDistinct--;
        }
        i++;
      }
      ans = Math.max(ans, j - i + 1);
    }
    return ans;
  }

  public int lengthOfLongestSubStringKDistinctIntegers(String s, int k) {
    return lengthOfLongestSubStringAtMostKDistinct(s, k)
        - lengthOfLongestSubStringAtMostKDistinct(s, k - 1);
  }