LeetCode: Longest Substring with At Most K Distinct Characters

// https://code.dennyzhang.com/longest-substring-with-at-most-k-distinct-characters
// Basic Ideas: sliding window
//
// Complexity: Time O(n*k), Space O(k)
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    res := 0
    m := map[byte]int{}
    // s[i...j]
    i:=0
    for j, ch := range s {
        // Move the right
        m[byte(ch)]++
        if m[byte(ch)] == 1 {
            k--
        }
        // Move the left
        for k<0 {
            ch2 := s[i]
            m[ch2]--
            i++
            if m[ch2] == 0 {
                k++
            }
        }
        // Collect result
        if j-i+1 > res {
            res = j-i+1
        }
    }
    return res
}

// https://code.dennyzhang.com/longest-substring-with-at-most-k-distinct-characters
// Basic Ideas: sliding window
//
// Complexity: Time O(n*k), Space O(k)
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    res := 0
    m := map[byte]int{}
    // s[i...j]
    i:=0
    for j, ch := range s {
        // Move the right
        m[byte(ch)]++
        // Move the left
        for len(m) > k {
            ch2 := s[i]
            m[ch2]--
            i++
            if m[ch2] == 0 {
                delete(m, ch2)
            }
        }
        // Collect result
        if j-i+1 > res {
            res = j-i+1
        }
    }
    return res
}

## https://code.dennyzhang.com/longest-substring-with-at-most-k-distinct-characters
## Basic Ideas:
##
## Complexity: Time O(n*k), Space O(k)
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        import collections
        import sys
        length = len(s)
        if length <= k: return length
        if k == 0: return 0
        d = collections.defaultdict(lambda: 0)
        index, res = length, -sys.maxsize-1
        for i in range(length):
            ch = s[i]
            if ch in d:
                d[ch] += 1
            else:
                if len(d) == k:
                    index = i
                    break
                else:
                    d[ch] += 1
        res = max(res, self.getCount(d))

        j = 0
        for i in range(index, length):
            d[s[i]] += 1
            while len(d) == k+1:
                ch = s[j]
                d[ch] -= 1
                j += 1
                if d[ch] == 0: del d[ch]
            res = max(res, self.getCount(d))
        return res

    def getCount(self, d):
        res = 0
        for ch in d: res += d[ch]
        return res