尽可能使字符串相等
思路
初次看到此题的描述,最直观的感受就是嵌套两层循环,进行字符比较ASCII码值的比较,同时与最大子字符串长度进行比较。
那么其实剥开此层皮,实际上我们可以发现本质就是通过一个int 数组来存放每个索引的字符串ASCII码的差值的绝对值,然后简化为对一个int数组,求连续元素和为target值的最大区间长度。很欣慰的是官方解法的双指针也是这么做的,嗨皮😨,最终简化为比如 数组
[1,2,2,3,3],target 为7,那么匹配的最长子区间为[2,2,3]长度为3
那么最终还是通过双指针来实现
代码实现
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int ans = 0, sum=0;
int len = s.length();
int left=0,right=0;
if(len==0) return ans;
int[] diff = new int[len]; // 此处就是通过int 数组存放对应索引位置的字符ascii差值的绝对值
for(int i=0;i<len;i++){
diff[i]=Math.abs(s.charAt(i)-t.charAt(i));
}
while(right<len){
sum += diff[right];
while (sum > maxCost) { //此处是通过 while 包一层循环,而不是if语句
sum -= diff[left];
left++;
}
ans = Math.max(ans, right - left + 1);
right++;
}
return ans;
}
}