题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个由 0 和 1 组成的字符串，现在找到其中最长连续子字符串的长度，要求字符串中间没有超过一个的相邻重复数字的情况。

思路分享

  • 经典不定长滑动窗口一则(【Leetcode Daily】3090每个字符最多出现两次的最长字符串)，不过本题有一点需要注意的是，判断相邻重复数字后的 left 指针的位置要清楚。如果像陆爻齐一样，left 判断完都会 ++ 那么就与灵茶山艾府的解法没那么一样，不能直接用 i-left+1，毕竟 left 其实一直在左窗口+1的位置上。

代码解答（强烈建议自行解答后再看）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int same_count = 0;
        int left = 1;
        int ans = 1;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == s[i-1]) {
                same_count++;
            }
            while (same_count > 1) {
                if (s[left] == s[left-1]) {
                    same_count--;
                }
                left++;
            }
            ans = max(ans, i-left+2);
        }
        return ans;
    }
};