leetcode 1234. 替换子串得到平衡字符串

题意：

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

Example 1:

输入：s = "QQQW"

输出：2

解释：我们可以把前面的 "QQ" 替换成 "ER"。

Example 2：

输入：s = "QQQQ"

输出：3

解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

思路：

从答案出发，目标是找出一个子串，替换它然后使得整个串中的四个字母的数量相同，假设最后的结果是替换子串s[i,j]（表示s中从第i个字符到第j个字符组成的子串），下面我们要做的就是如何搜索出i和j的值，使得j-i尽可能小，首先想到的就是暴力求解，枚举出所有的i和j，判断是否满足要求，在满足要求的基础上取最小值，时间复杂度 $O (n^$ ，超时是逃不了的，但是这里很容易想到解决办法：二分搜索！，确定i，使用二分搜索j，时间复杂度O(nlogn)，这样就能AC了。

 1 const int N=1e5+10;
 2 class Solution {
 3 public:
 4     int sol(char c){
 5         if(c=='Q')return 0;
 6         else if(c=='W')return 1;
 7         else if(c=='E')return 2;
 8         return 3;
 9     }
10     int a[N][4];
11     bool f[4];
12     int balancedString(string s) {
13         int n=s.size();
14         for(int i=0;i<n;i++){
15             a[i+1][0]=a[i][0]; a[i+1][1]=a[i][1]; a[i+1][2]=a[i][2]; a[i+1][3]=a[i][3];
16             if(s[i]=='Q')a[i+1][0]++;
17             else if(s[i]=='W')a[i+1][1]++;
18             else if(s[i]=='E')a[i+1][2]++;
19             else a[i+1][3]++;
20         }
21         int ans=0x3f3f3f3f;
22         for(int i=0;i<=n;i++){
23             int l=i,r=n;
24             while(l<=r){
25                 int mid=(l+r)/2;
26                 bool f=true;
27                 for(int j=0;j<4;j++){
28                     if(a[i][j]+a[n][j]-a[mid][j]>n/4){f=false; break;}
29                 }
30                 if(f)r=mid-1;
31                 else l=mid+1;
32             }
33             r++;
34             if(r!=n+1)ans=min(ans,r-i);
35             if(ans==0)return 0;
36         }
37         return ans;
38     }
39 };

View Code