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

题目描述#

给你一个下标从 0 开始的字符串 s，只包含数字字符。如果一个字符串 t 中至多有一对相邻字符是相等的，则称 t 是半重复的。返回 s 中最长半重复子字符串的长度。

核心思想#

不定长滑动窗口，维护窗口内相邻相同字符对数 cnt_dup。

窗口合法的充要条件是 cnt_dup ≤ 1。

状态转移：

右端点 right 进入窗口：若 s[right] == s[right-1]，则 cnt_dup += 1（新增一对相邻相同）
左端点 left 离开窗口：若 s[left] == s[left+1]，则 cnt_dup -= 1（移除一对相邻相同）

当 cnt_dup > 1 时，不断右移 left 直到 cnt_dup ≤ 1。

算法步骤#

初始化 left = 0, cnt_dup = 0, ans = 0
遍历 right 从 0 到 n-1：
- 若 right > 0 且 s[right] == s[right-1]，cnt_dup += 1
- 当 cnt_dup > 1 时：
  - 若 s[left] == s[left+1]，cnt_dup -= 1
  - left += 1
- 更新 ans = max(ans, right - left + 1)
返回 ans

逐步举例#

以 s = "1111" 为例，n = 4：

right	s[right]	s[right]==s[right-1]?	cnt_dup	收缩过程	left	ans
0	’1’	—	0	—	0	1
1	’1’	是	1	—	0	2
2	’1’	是	2	s[0]==s[1]→cnt=1,l=1	1	2
3	’1’	是	2	s[1]==s[2]→cnt=1,l=2	2	2

最终 ans = 2（最长半重复子串为 "11"）。

复杂度分析#

时间复杂度：O(n)。left 和 right 各遍历一次，每个元素最多被访问两次。
空间复杂度：O(1)。仅用常数个变量。

参考#

灵茶山艾府：找到最长的半重复子字符串

代码实现#

1
class Solution:
2
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
3
        ans = left = cnt = 0
4
        for right in range(len(s)):
5
            if right > 0 and s[right] == s[right - 1]:
6
                cnt += 1
7
            while cnt > 1:
8
                if s[left] == s[left + 1]:
9
                    cnt -= 1
10
                left += 1
11
            ans = max(ans, right - left + 1)
12
        return ans

1
import sys
2
sys.path.insert(0, "/workspace/projects/source/coding/sliding-window-two-pointers/02-variable-sliding-window/2730-semi-repetitive")
3
from solution import Solution
4
import unittest
5

6
class TestSemiRepetitive(unittest.TestCase):
7
    def setUp(self):
8
        self.solution = Solution()
9

10
    def test_example1(self):
11
        self.assertEqual(self.solution.longestSemiRepetitiveSubstring("52233"), 4)
12

13
    def test_example2(self):
14
        self.assertEqual(self.solution.longestSemiRepetitiveSubstring("5494"), 4)
15

16
    def test_example3(self):
17
        self.assertEqual(self.solution.longestSemiRepetitiveSubstring("1111111"), 2)
18

19
    def test_single(self):
20
        self.assertEqual(self.solution.longestSemiRepetitiveSubstring("1"), 1)
21

22
    def test_no_repeat(self):
23
        self.assertEqual(self.solution.longestSemiRepetitiveSubstring("12345"), 5)
24

25
if __name__ == "__main__":
26
    unittest.main()