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
}