题目链接：1234. 替换子串得到平衡字符串
题目内容：
题目中给出了平衡字符串的定义——只有’Q’，‘W’，‘E’，'R’四种字符，并且每种字符的数量都是n/4。但是现在给出一个字符串s，它不一定是平衡字符串。如果不是就要通过替换其中一个子串，使其成为平衡字符串。将字符串s看作是待替换部分s1和剩下的部分s2，将s1替换成其他字符串后，能够保证新的s1插入s2后四种字符的数量都是n/4。新的s1插入s2只能增加字符的数量而不能减少字符的数量，因此s2中四种字符的数量均要≤n/4。
这个题目使用滑动窗口，滑动窗口内的子串即待删除的s1。其下标用left和right表示，s1是s中[left，right)这一段子串。滑动窗口滑动的过程如下：
代码如下（C++）：
class Solution {
public:
//判断四种字符的数量是否均≤n/4
bool check(vector<int>& cnt , int num){
if(cnt['Q' - 'A'] > num
||cnt['E' - 'A'] > num
||cnt['W' - 'A'] > num
||cnt['R' - 'A'] > num)
return false;
return true;
}
int balancedString(string s) {
//先统计s中四种字符的数量
vector<int> cnt(26,0);
for(char ch : s)
cnt[ch-'A']++;
int num = s.size() / 4;
//如果一开始就小于等于【实际上是等于】就直接返回0，不需要替换
if(check(cnt, num))
return 0;
//记录最小长度
int ans = s.size();
//滑动窗口更新过程
for(int left = 0, right = 0; left < s.size(); left++){
//right右移直到滑动窗口外四种四字符均≤n/4
while(right < s.size() && !check(cnt, num)){
cnt[s[right] - 'A']--;
right++;
}
//上面循环结束可能是right=s.size()，也可能是满足条件了
//如果是right=s.size()了，right不能右移了，之后left右移的过程中只能使得滑动窗口外四种字符的数量增加
//如果一旦有left使得有字符数量＞n/4，left继续右移已经没有意义，之后的滑动窗口都不满足要求，提前跳出循环
if(!check(cnt,num))
break;
//更新长度
ans = min(ans, right - left);
cnt[s[left] - 'A']++;
}
return ans;
}
};
题目链接：680. 验证回文串
题目内容：
判断一个字符串是否是回文串的时候，使用的是双指针，一个left从下标0开始，一个right从s.size()-1开始，然后如果s[left] == s[right]，left++，right–；直到left >= right，遍历完s中的字符。
现在题目是要求我们最多删除一个字符串，判断s是否是回文串。此时有三种情况：
代码如下（C++）：
class Solution {
public:
//判断left~right这一段子串是否是回文串
bool ispalindrome(int left, int right, string& s){
while(left<right){
if(s[left] != s[right])
return false;
left++;
right--;
}
return true;
}
bool validPalindrome(string s) {
int left = 0, right = s.size()-1;
//前后逐字符对比
while(left < right){
//如果相等就left++，right--
if(s[left] == s[right]){
left++;
right--;
}
//如果不相等，就去判断left~right-1和left+1~right这两段子串是否是回文串
else
return ispalindrome(left,right - 1,s) || ispalindrome(left+1,right,s);
}
return true;
}
};
题目链接：917. 仅仅反转字母
题目内容：
题目说的是英文字母位置反转。看题目以为这个位置反转和之前的反转单词一样，只是把非英文的字符当作单词的分隔符……结果原来是和这个反转字符串类似。只是遇到非英文字母的字符直接跳过不处理。
先看看例子：
因此这里的位置反转，也是双指针left和right，在s[left]和s[right]都是英文字母的时候，二者交换；如果不是英文字母就跳过，不处理，代码如下（C++）：
class Solution {
public:
//判断是否是英文字母
bool check_ch(char ch){
if(ch - 'a' >= 0 && ch - 'a' < 26)
return true;
if(ch - 'A' >= 0 && ch - 'A' < 26)
return true;
return false;
}
string reverseOnlyLetters(string s) {
//双指针遍历s中每个字符
for(int i = 0, j = s.size() -1 ; i < j;){
//s[i]和s[j]都是英文字母的时候，交换位置
if(check_ch(s[i]) && check_ch(s[j])){
swap(s[i],s[j]);
i++;
j--;
}
else {
//不是英文字母就跳过
if(!check_ch(s[i]))
i++;
if(!check_ch(s[j]))
j--;
}
}
return s;
}
};