技巧:
尺取 + 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)
} 
京公网安备 11010502036488号