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)