编程题2

官方题解的GO版本

package main

import(
    "fmt"
    "bufio"
    "os"
)

func main() {
    var n, m int
    fmt.Scan(&n)
    fmt.Scan(&m)
    reader := bufio.NewReaderSize(os.Stdin, n)
    line, _, _ := reader.ReadLine()
//     fmt.Println(max(arraySolve(n, m, line, 'a'), arraySolve(n, m, line, 'b')))
    fmt.Println(windowSolve(line, m, n))
}

func arraySolve(n, m int, s []byte, c byte) int {
    res := 0
    indexes := make([]int, 0) //存储所有的a/b字符的下标
    for i := 0; i < n; i++ {
        if s[i] == c {
            indexes = append(indexes, i)
        }
    }

    // 全部替换即可
    if len(indexes) <= m {
        return n
    }

    // 在最后面补一位,防止漏掉最后一个连续子串的情形
    indexes = append(indexes, n)
    // indexes[m]表示前面刚好有m个a/b,将它们全部替换掉得到的子串长度res即为indexes[m]指向的下标
    res = indexes[m]
    for i := m+1; i < len(indexes); i++ {
        // indexes[i] 与 indexes[i-m-1]之间共有m+1个a/b,而indexes[i-m-1]本身就是a/b,因此再减去1,就可以得到最长子串
        res = max(res, indexes[i]-indexes[i-m-1]-1)
    }
    return res
}

func windowSolve(str []byte, m, n int) int {
    var res int
    left, right := 0, 0
    cntA, cntB := 0, 0 
    for right < n {
        if str[right] == 'a' {
            cntA++
        } else {
            cntB++
        }
        if cntA > m && cntB > m {
            res = max(res, right-left)
            if str[left] == 'a' {
                cntA--
            } else {
                cntB--
            }
            left++
        }
        right++
    }
    res = max(res, right-left)
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

package main

import(
    "fmt"
)

func main(){
    n,m := 0,0
    var str string
    fmt.Scanln(&n,&m)
    fmt.Scanln(&str)
    arr := []byte(str)
    pair := [2]int{}
    res := 0
    for l,r := 0,0; l <= r;{
//      右指针前移   
        for r < len(arr) && (pair[0] <= m || pair[1] <= m){
            if arr[r] == 'a'{
                pair[0]++
            }else{
                pair[1]++
            }
            r++
        }
//      子解   
        if r-l-1 > res{
            res = r-l-1
        }
//      右指针到头，子解变小，无效子解   
        if r == len(arr){
            break
        }
//      左指针前移   
        if arr[l] == 'a'{
            pair[0]--
        }else{
            pair[1]--
        }
        l++
    }
    fmt.Println(res)
}