今天的每日寫過了
改寫別題
1234. Replace the Substring for Balanced String
先算出Q、W、E、R各自的數量
再算已經平衡的組數、還沒平衡的組數
接著把Q、W、E、R各自的數量 - 已經平衡的組數
如果 > 0那就是多餘的字母，可以替換成別的字母
接著就用slinding window找出長度最短且含有多於字母的子字串
golang code :
func balancedString(s string) int {
n := len(s)
rec := make([]int, 4)
start, ans := 0, n+1
for i := 0; i < n; i++ {
idx := findIdx(s[i])
rec[idx]++
}
curBalanceNum := min(rec[0], rec[1], rec[2], rec[3])
unBalanceNum := n/4 - curBalanceNum
if unBalanceNum == 0 {
return 0
}
need, cnt, curNum := make([]int, 4), 0, []int{0, 0, 0, 0}
for i := 0; i < 4; i++ {
need[i] = max(0, rec[i]-curBalanceNum-unBalanceNum)
if need[i] == 0 {
cnt++
}
}
for i := 0; i < n; i++ {
idx := findIdx(s[i])
curNum[idx]++
if need[idx] != 0 && curNum[idx] == need[idx] {
cnt++
}
for cnt == 4 {
ans = min(ans, i-start+1)
idx = findIdx(s[start])
curNum[idx]

別卷了