Leetcode - Longest Substring with At Most K Distinct Characters

Leetcode - Longest Substring with At Most Two Distinct Characters

violet posted @ May 15, 2020 08:56:06 AM in 算法 with tags Algorithm Golang array , 304 阅读

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

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

func lengthOfLongestSubstringTwoDistinct(s string) int {
    if len(s) == 0 || len(s) == 1 {
        return len(s)
    }
    hash := map[byte]int{}
    first := s[0]
    second := s[0]
    firstIndex := 0
    secondIndex := 0
    i := 0
    j := i + 1
    max := 0
    for j < len(s) {
        first = s[i]
        firstIndex = i
        j = i
        
        for j < len(s) && len(hash) < 3 {
            if _, ok := hash[s[j]]; !ok && len(hash) == 2 {
                break
            }
            if s[j] != first {
                second = s[j]
            }
            if s[j] == first {
                firstIndex = j
            }
            if s[j] == second {
                secondIndex = j
            }
            hash[s[j]]++
            j++
        }
        
        tmp := j - i
        if tmp > max {
            max = tmp
        }
        if firstIndex < secondIndex {
            i = firstIndex + 1
            delete(hash, first)
        } else {
            i = secondIndex + 1
            delete(hash, second)
        }
    }
    return max
}