class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
}
};
6425. 找到最长的半重复子字符串
给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串是 半重复的 。
请你返回 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'原站题解
python3 解法, 执行用时: 64 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-11 09:04:18
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
n, left, right, res, p = len(s), 0, 1, 1, 0
while right < n:
if s[right] == s[right-1]:
p = right
while right < n - 1 and s[right] != s[right+1]:
right += 1
res = max(res, right - left + 1)
left, right = p, right + 1
return res
java 解法, 执行用时: 6 ms, 内存消耗: 43.1 MB, 提交时间: 2023-06-11 09:03:40
class Solution {
public int longestSemiRepetitiveSubstring(String s) {
int preLeft = -1, left = 0, maxLen = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
left = preLeft == -1 ? 0 : preLeft;
preLeft = i;
}
maxLen = Math.max(maxLen, i - left + 1);
}
return maxLen;
}
}
python3 解法, 执行用时: 84 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-11 09:03:09
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
n=len(s)
pos=[-1]
for i in range(n-1):
if s[i]==s[i+1]:
pos.append(i)
pos.append(n-1)
m=len(pos)
if m>=3:
return max([pos[i]-pos[i-2] for i in range(2,m)])
else:
return n
cpp 解法, 执行用时: 20 ms, 内存消耗: 6.2 MB, 提交时间: 2023-06-11 09:02:43
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
int n = s.size();
int res = 0;
int left = 0;
int conflict = 0;
for (int right = 0; right < n; ++right) {
if (right > 0 && s[right] == s[right - 1]) {
++conflict; // 拓张窗口
while (conflict > 1) {
if (s[left] == s[left + 1]) {
--conflict;
}
++left; // 收缩窗口
}
}
res = max(res, right - left + 1); // 更新答案
}
return res;
}
};
cpp 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-06-11 09:02:16
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
int left=0,flag=0;
int Max=0;
int len=s.size();
for(int i=1;i<s.size();i++)
{
if(s[i]==s[i-1])
{
if(flag==0)
flag=i;
else{
Max=max(Max,i-left);
left=flag;
flag=i;
}
}
}
Max=max(Max,len-left);
return Max;
}
};
python3 解法, 执行用时: 96 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-11 09:01:57
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
lens, lst = len(s), [x == y for x, y in pairwise(s)]
for n in range(lens - 1, -1, -1):
for i in range(lens - n):
if lst[i: i + n].count(True) <= 1:
return n + 1