2730-找到最长的半重复子字符串

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，0010 、002020
、0123 、2002 和 54944 是半重复字符串，而 00101022 和 1101234883 不是。

请你返回 s 中最长 半重复 子字符串的长度。

一个 子字符串 是一个字符串中一段连续 非空 的字符。

示例 1：

**输入：** s = "52233"
**输出：** 4
**解释：** 最长半重复子字符串是 "5223" ，子字符串从 i = 0 开始，在 j = 3 处结束。

示例 2：

**输入：** s = "5494"
**输出：** 4
**解释：** s 就是一个半重复字符串，所以答案为 4 。

示例 3：

**输入：** s = "1111111"
**输出：** 2
**解释：** 最长半重复子字符串是 "11" ，子字符串从 i = 0 开始，在 j = 1 处结束。

提示：

• 1 <= s.length <= 50
• '0' <= s[i] <= '9'

前置知识：同向双指针（滑动窗口）

见【基础算法精讲 01】 。

思路

移动右指针 right，并统计相邻相同的情况出现了多少次，记作 same

如果 same}>1，则不断移动左指针 left 直到 s[\textit{left}]=s[\textit{left}-1]，此时将一对相同的字符移到窗口之外。然后将 same 置为 1。

然后统计子串长度 right}-\textit{left}+1 的最大值。

[sol-Python3]

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        ans, left, same = 1, 0, 0
        for right in range(1, len(s)):
            same += s[right] == s[right - 1]
            if same > 1:
                left += 1
                while s[left] != s[left - 1]:
                    left += 1
                same = 1
            ans = max(ans, right - left + 1)
        return ans

[sol-Java]

class Solution {
    public int longestSemiRepetitiveSubstring(String S) {
        var s = S.toCharArray();
        int ans = 1, left = 0, same = 0, n = s.length;
        for (int right = 1; right < n; right++) {
            if (s[right] == s[right - 1] && ++same > 1) {
                for (left++; s[left] != s[left - 1]; left++);
                same = 1;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int ans = 1, left = 0, same = 0, n = s.length();
        for (int right = 1; right < n; right++) {
            if (s[right] == s[right - 1] && ++same > 1) {
                for (left++; s[left] != s[left - 1]; left++);
                same = 1;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

[sol-Go]

func longestSemiRepetitiveSubstring(s string) int {
	ans, left, same := 1, 0, 0
	for right := 1; right < len(s); right++ {
		if s[right] == s[right-1] {
			same++
			if same > 1 {
				left++
				for s[left] != s[left-1] {
					left++
				}
				same = 1
			}
		}
		ans = max(ans, right-left+1)
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 s 的长度。注意 left 只会增加不会减少，所以二重循环的时间复杂度为 \mathcal{O}(n)。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。