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

题目：

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

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

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

思路：

代码：

class Solution {public int longestSemiRepetitiveSubstring(String s) {char[] ch = s.toCharArray();int n = ch.length;int ans = 1;int left = 0;int cnt = 0;for (int right = 1; right < n; right++) {if (ch[right] == ch[right - 1] && ++cnt > 1) {// 关键部分 注意left++// 把left移动到前一对重复出现的二人的右边for(left++; ch[left] != ch[left - 1]; left++);cnt = 1;}ans = Math.max(ans, right - left + 1);}return ans;}
}

性能：

时间复杂度o（n）

空间复杂度o（1）