代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 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'
我们用双指针维护一个区间 $s[j..i]$,使得区间内最多只有一个相邻字符相等。我们用 $cnt$ 记录区间内相邻字符相等的个数,如果 $cnt \gt 1$,那么我们就需要移动左指针 $j$,直到 $cnt \le 1$。每一次,我们更新答案为 $ans = \max(ans, i - j + 1)$。
时间复杂度 $O(n)$,其中 $n$ 是字符串的长度。空间复杂度 $O(1)$。
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
n = len(s)
ans = cnt = j = 0
for i in range(n):
if i and s[i] == s[i - 1]:
cnt += 1
while cnt > 1:
if s[j] == s[j + 1]:
cnt -= 1
j += 1
ans = max(ans, i - j + 1)
return ans
class Solution {
public int longestSemiRepetitiveSubstring(String s) {
int n = s.length();
int ans = 0;
for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
++cnt;
}
while (cnt > 1) {
if (s.charAt(j) == s.charAt(j + 1)) {
--cnt;
}
++j;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
int n = s.size();
int ans = 0;
for (int i = 0, j = 0, cnt = 0; i < n; ++i) {
if (i && s[i] == s[i - 1]) {
++cnt;
}
while (cnt > 1) {
if (s[j] == s[j + 1]) {
--cnt;
}
++j;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
func longestSemiRepetitiveSubstring(s string) (ans int) {
n := len(s)
for i, j, cnt := 0, 0, 0; i < n; i++ {
if i > 0 && s[i] == s[i-1] {
cnt++
}
for cnt > 1 {
if s[j] == s[j+1] {
cnt--
}
j++
}
ans = max(ans, i-j+1)
}
return
}
function longestSemiRepetitiveSubstring(s: string): number {
const n = s.length;
let ans = 0;
for (let i = 0, j = 0, cnt = 0; i < n; ++i) {
if (i > 0 && s[i] === s[i - 1]) {
++cnt;
}
while (cnt > 1) {
if (s[j] === s[j + 1]) {
--cnt;
}
++j;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。