LeetCode 滑动窗口 每个字符最多出现两次的最长子字符串

每个字符最多出现两次的最长子字符串

给你一个字符串 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;
}

原文地址：https://blog.csdn.net/2301_80293400/article/details/142467024

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！