【leetcode 力扣刷题】删除字符串中的子串or字符以满足要求

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

题目链接：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)这一段子串。滑动窗口滑动的过程如下：

• 1、先固定left，然后right向右移动，移动的同时字符s[right]的数量-1，直到四种字符数量均≤n/4——此时找到了[left，right)这一段s1，使得s中除s1外，四种字符数量均≤n/4；
• 2、此时逐步右移left，缩小滑动窗口（即s1）的长度，以便找到最短的s1；同时字符s[left]的数量+1，并判s-s1中四种字符的数量是否均≤n/4；
• 3、每找到一个满足条件的[left，right)滑动窗口，就需要记录窗口的长度，并记录最小值；

代码如下（C++）：

class Solution {
public://判断四种字符的数量是否均≤n/4bool 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/4while(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. 验证回文串

题目链接：680. 验证回文串
题目内容：

判断一个字符串是否是回文串的时候，使用的是双指针，一个left从下标0开始，一个right从s.size()-1开始，然后如果s[left] == s[right]，left++，right–；直到left >= right，遍历完s中的字符。
现在题目是要求我们最多删除一个字符串，判断s是否是回文串。此时有三种情况：

• 1、s本身就是回文串，能够按照上述的判断过程逐字符对比判断；
• 2、s本身不是回文串，但是删除一个字符后能够是回文串：s不是回文串，肯定会出现s[left] !=s [right]，此时要么删除s[left]，然后判断s[left+1~right]是否是回文串；要么删除s[right]，判断s[left~right-1]是否是回文串； 这两个只要有一个是回文串即可；【也可能两个都是回文，比如acac删除a得到cac，删除c得到aca，都是回文】
• 3、s不是回文串，不管删除哪个字符都不能成为回文串——上述第二种情况中，如果不管删除s[left]还是s[right]，剩下的都不是回文串，那么如果考虑继续遍历，删除其他字符串，但是s[left] != s[right]，不管再去删除s[left+1~right-1]中的哪个字符，都不能使得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. 仅仅反转字母

题目链接：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;}
};