每个字符最多出现两次的最长子字符串
给你一个字符串 s ,请找出满足每个字符最多出现两次的最长子字符串,并返回该
子字符串
的 最大 长度。
示例 1:
输入: s = “bcbbbcba”
输出: 4
解释:
以下子字符串长度为 4,并且每个字符最多出现两次:“bcbbbcba”。
示例 2:
输入: s = “aaaa”
输出: 2
解释:
以下子字符串长度为 2,并且每个字符最多出现两次:“aaaa”。
提示:
2 <= s.length <= 100
s 仅由小写英文字母组成。
题解
本体需要找到满足条件的最长子字符串,所以我们使用滑动窗口进行解题
由于最长子字符串的长度未知,所以滑动窗口是不定长滑动窗口
我们分别用 l 与 r 代表滑动窗口的左边有右边界(这里采用的有效窗口区域不包括 r 的位置)
采用一个数组 arr 对窗口中出现过的字母的次数进行统计
定义 int res = 2 记录返回值
然后循环遍历字符串直到 r == strlen(s) 退循环
循环过程中假如 arr[s[r]-‘a’] < 2 则 r++
否则说明该字母已经出现过两次了
arr[s[l]-‘a’]–
l++
在一次更新完窗口之后子字符串的长度为 r-l 找到最大的 r-l 赋给 res 即可
代码如下↓
int maximumLengthSubstring(char* s) {int l=0,r=1;int arr[26];memset(arr,0,sizeof(arr));arr[s[l]-'a']++;int res = 2;while(r<strlen(s)){if(arr[s[r]-'a']<2){arr[s[r]-'a']++;r++;}else{arr[s[l]-'a']--;l++;}if(r-l>res){res = r-l;}}return res;
}