What defines a semi-repetitive substring in this problem?

A semi-repetitive substring contains at most one pair of consecutive identical digits, any more breaks the rule.

Can the entire string be semi-repetitive?

Yes, if the string contains at most one adjacent repeated pair, the entire string can be counted as the longest substring.

Is a sliding window necessary for small inputs?

Not strictly; for s.length up to 50, a brute-force check of every substring works but sliding window is more efficient and scalable.

How do I handle multiple adjacent repeats?

Stop expanding the window when a second adjacent repeat appears, then move the start pointer past the first repeat to maintain semi-repetitive property.

Does this solution pattern apply to other strings?

Yes, the sliding window with running state updates can be applied to any sequence where you need to track limited repeated patterns.

#2730

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是半重复的。例如， "0010" 、 "002020" 、 "0123" 、 "2002" 和 "54944" 是半重复字符串，而 "001…

字符串滑动窗口

题目描述

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

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

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

示例 1：

输入：s = "52233"

输出：4

解释：

最长的半重复子字符串是 "5223"。整个字符串 "52233" 有两个相邻的相同数字对 22 和 33，但最多只能选取一个。

示例 2：

输入：s = "5494"

输出：4

解释：

s 是一个半重复字符串。

示例 3：

输入：s = "1111111"

输出：2

解释：

最长的半重复子字符串是 "11"。子字符串 "111" 有两个相邻的相同数字对，但最多允许选取一个。

提示：

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

lightbulb

解题思路

方法一：双指针

我们用双指针维护一个区间 $s[j..i]$ ，使得区间内最多只有一个相邻字符相等，初始时 $j = 0$ , $i = 1$ 。初始化答案 $ans = 1$ 。

我们用 $cnt$ 记录区间内相邻字符相等的个数，如果 $cnt \gt 1$ ，那么我们就需要移动左指针 $j$ ，直到 $cnt \le 1$ 。每一次，我们更新答案为 $ans = \max(ans, i - j + 1)$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        ans, n = 1, len(s)
        cnt = j = 0
        for i in range(1, n):
            cnt += s[i] == s[i - 1]
            while cnt > 1:
                cnt -= s[j] == s[j + 1]
                j += 1
            ans = max(ans, i - j + 1)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) using the sliding window because each character is visited at most twice. Space complexity is O(1) as only counters and two pointers are needed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate must handle the edge case where all digits are identical.
question_mark
Look for efficient tracking of repeated adjacent digits within the window.
question_mark
Watch if the candidate correctly resets the window after the second repeat occurs.

warning

常见陷阱

外企场景

error
Counting repeated pairs incorrectly and allowing more than one in the window.
error
Failing to update the maximum length after shifting the window.
error
Not handling the first or last character correctly when checking adjacent repeats.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest substring allowing up to k adjacent repeated pairs instead of 1.
arrow_right_alt
Count the number of longest semi-repetitive substrings instead of returning length.
arrow_right_alt
Apply the same logic to a string with letters instead of digits, still using the semi-repetitive rule.

help

常见问题

外企场景

继续练习

#2781 最长合法子字符串的长度 #2904 最短且字典序最小的美丽子字符串 #2516 每种字符至少取 K 个