340. Longest Substring with At Most K Distinct Characters (sliding window, hashmap, two pointers),

159 is the same to this

time: O(n)

space: O(1)

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int max = 0;
        int count[] = new int[256];
        int num = 0; // record kind of chars
        int j = 0; // left
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] == 0) {
                num++;
            }
            count[s.charAt(i)]++;
            
            // left: j start to move k size windows, 
            // when j move, count[j]--, if 0 means, kind of char --
            while (num > k && j < s.length()) {
                count[s.charAt(j)]--;
                if (count[s.charAt(j)] == 0) {
                    num--; // make k size windows fit to k
                }
                j++;
            }
            
            max = Math.max(max, i - j + 1);   
        }
        return max;
    }
}

/*
count[] record char count
num - how many different kind of char
int j = 0, left
"eceba"
   j
    i
 
  count[e] = 2; 
  count[c] = 1; num = 2;
  count[b] = 1; num = 3
 if (num > k) { // maintain k size, let k size -1
    while (count[j] > 0) {
        count[j]--
        j++
    }
 }  
 
 
 max = i - j +1 = 3
      
*/

latest

```java
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        int left = 0;
        int result = 0;
        Map<Character, Integer> freqMap = new HashMap<>();

        for (int right = 0; right < n; right++) {
            char rightChar = s.charAt(right);
            freqMap.put(rightChar, freqMap.getOrDefault(rightChar, 0)+1);

            while (left <= right && freqMap.size() > k) {
                char leftChar = s.charAt(left);
                freqMap.put(leftChar, freqMap.getOrDefault(leftChar, 0)-1);
                if (freqMap.get(leftChar) == 0) {
                    freqMap.remove(leftChar);
                }
                left++;
            }
            result = Math.max(result, right - left + 1);
        }
        return result;
    }
}

/**

at most k

> k
left++


abee
 */
```