前缀和与二分查找的应用

给出一个只有’F’ 和 ‘T’ 的字符串，和一个整数 k，可以对字符串种的字符进行两种修改：1. 把 ‘T’ 变为 ‘F’ ，2. 把 ‘F’ 变为 ‘T’。最多能修改 k 次，求由相同字符组成的连续子串长度的最大值。

例如：

1 2	"TTFF", k = 2 可以变为 "TTTT"，返回 4

1 2	"TFFT", k = 1 可以变为"FFFT"，返回 3

从该题可以学到：

前缀和思想
二分查找思想

前缀和

前缀和是一种常用的预处理技术，可以在 O(1) 内进行查询。例如给出一个字符串 “TTFTTFTT”，任意给出一个范围，分别求该范围内 T 的个数和F的个数。通常情况下，需要 O(n) 来遍历计算。如果查询次数很大，可以在 O(n) 内获得前缀和，在之后的每次查询中，只需 O(1) 时间复杂度。

获取前缀和代码：字符串用 answerKey 表示，d 数组存储前缀和，大小为字符串长度+1。

int d[50005];  
for(int i=0; i<len; ++i){
		d[i+1] = d[i] + (answerKey[i]=='T'?1:0); 
}

answerKey =”TTFTTFTT”

前缀和为 0 1 2 2 3 4 4 5 6

d[x]-d[0] 表示下标 0 到 x 范围内 T 的个数，用 w 表示，用该范围内字符总数减去 T 的个数，就是 F 的个数，即 x - (d[x]-d[0])，用 x-w 表示。

根据题意，给一个范围内，我们取 x 和 x-w 的最小值 minum，如果 minum 大于 k，说明范围太大了，不能在 k 次内将子串修改为相同字符。如果 minum 小于等于 k，说明该范围完全可以在 k 次修改变成相同字符，在继续扩大范围，以相同方式判断。直到不能将范围扩大为止。

可以看到前缀和为递增数列，所有可能的范围如下，为了快速找到正确的右边界，很明显可以使用二分查找。

二分查找

二分查找是一种快速的查找算法，它的时间复杂度为 O(lg n)。需要待查找数组有序。

由上图可知，所有可能的范围的右边界是递增的。我们可以根据中间位置判断正确答案在左边还是右边。

中间位置判断：

bool binary(int x){
		for(int i=x; i<=len; ++i){
				int w = d[i] - d[i-x];
    		if(min(w,x-w)<= k) return true;   // w: T的个数   x-w: F 的个数
    }
    return false;
}

只要以下的任何一种满足，右边界就在中间值的右边，否则在左边。

二叉查找代码：

int l=1,r=len;
while(l<r){
		int mid=(l+r+1)>>1;     // 防止死循环
		if(judge(mid)) l = mid;
		else r = mid-1;
}

完整代码如下

class Solution {
public:
    int d[50005];
    int k;
    int len;
    bool judge(int x){
        for(int i=x; i<=len; ++i){
            int w = d[i] - d[i-x];
            if(min(w,x-w)<=k) return true;   // w: T的个数   x-w: F 的个数
        }
        return false;
    }
    int maxConsecutiveAnswers(string answerKey, int k) {
        this->k = k;
        len = answerKey.size();
        for(int i=0; i<len; ++i){
            d[i+1] = d[i] + (answerKey[i]=='T'?1:0); 
        }
        int l=1,r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(judge(mid)) l = mid;
            else r = mid-1;
        }
        return l;
    }
};

如有遗漏，欢迎指正。