技巧:
尺取 + 01串辅助模型
思路:
当凑不齐26字母时候右指针向右侧移动
当凑齐26字母时候左指针尽量向右移动
如何看是或凑齐字母? 维护有个二进制串 初始为11111111 ,每一位代表一个字母。发现一个字符就将其变成0 。当全0时候说明凑齐。
左指针向右移动时候需要维护一下当前区间内剩余字符的数量。
实现:
package main import ( "fmt" ) func main() { var str string fmt.Scan(&str) k := ^uint32(0) >> (32 - 26) // 是否集齐26个字母 m := make(map[byte]int) // 在l r区间里面重复字符数量 ans := int(^uint32(0) >> 1) l, r := 0, 0 for r < len(str) { for k != 0 && r < len(str) { m[str[r]] = m[str[r]] + 1 k = k & (^(1 << (str[r] - 'a'))) // 将str[r] - 'a'位上变成0 r++ continue } for k == 0 { if r-l < ans { ans = r - l } if m[str[l]] == 1 { delete(m, str[l]) k = k | (1 << (str[l] - 'a')) // 将str[r] - 'a'位上变成1 } else { m[str[l]] = m[str[l]] - 1 } l++ } } fmt.Println(ans) }