0340. Longest Substring with At Most K Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters

Description

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

**Input:** s = "eceba", k = 2
**Output:** 3
**Explanation:** The substring is "ece" with length 3.

Example 2:

**Input:** s = "aa", k = 1
**Output:** 2
**Explanation:** The substring is "aa" with length 2.

Constraints:

• 1 <= s.length <= 5 * 104

• 0 <= k <= 50

ac: window problem in string

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // edge cases
        if (s == null || s.length() == 0 || k <= 0) return 0;

        // build note
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int l = 0, r = 0, lgst = 0, cnt = 0;

        // iterate
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) == 1) cnt++;  // new character appear in current window

            while (cnt > k) {  // one window formed
                lgst = Math.max(lgst, r - l);  // store length
                char lc = s.charAt(l);
                map.put(lc, map.get(lc) - 1);
                l++;  // remove left char, move window

                if (map.get(lc) == 0) cnt--;  // reduce one char count 
            }
        }
        lgst = Math.max(lgst, r - l);  // update last window value

        // result
        return lgst;
    }
}