1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| // @Title: 尽可能使字符串相等 (Get Equal Substrings Within Budget)
// @Author: 15816537946@163.com
// @Date: 2021-02-05 22:11:34
// @Runtime: 0 ms
// @Memory: 3.8 MB
// 双指针
func equalSubstring(s string, t string, maxCost int) int {
n := len(s)
diff := make([]int, n)
for i, ch := range s {
diff[i] = abs(int(ch) - int(t[i]))
}
sum, start := 0, 0
var maxLen int
for end, d := range diff {
sum += d
if sum > maxCost {
sum -= diff[start]
start++
}
maxLen = max(maxLen, end-start+1)
}
return maxLen
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
|