Leetcode - Longest Substring with At Most K Distinct Characters

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

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

func lengthOfLongestSubstringKDistinct(s string, k int) int {
    if len(s) == 0 || k == 0 {
        return 0
    }
    i := 0
    j := i
    hash := map[byte]int{}
    max := 0
    for j < len(s) {
        for j < len(s) {
            if _, ok := hash[s[j]]; !ok {
                if len(hash) == k {
                    break
                } 
                hash[s[j]] = j
            } else {
                hash[s[j]] = j
            }
            j++
        }
        //fmt.Println("hash: ", hash)
        //fmt.Println("i, j: ", i, j)
        if max < j - i {
            max = j - i
        }
        if j >= len(s) {
            break
        }
        min := j
        minK := s[j]
        for key, val := range hash {
            if min > val {
                min = val
                minK = key
            }
        }
        delete(hash, minK)
        i = min + 1
    }
    if j - i > max {
        max = j - i
    }
    return max
}

Time complexity: O(n*k)

Space complexity: O(k)

• 相关文章
• 全局相关文章