3090. 每个字符最多出现两次的最长子字符串#

题目描述#

给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

1
输入：s = "bcbbbcba"
2
输出：4

示例 2：

1
输入：s = "aaaa"
2
输出：2

解法思路#

核心思想#

这是一个不定长滑动窗口问题（越短越合法）。窗口内每个字符的出现次数都 $\le 2$ 是合法条件。右指针不断把新字符纳入窗口；一旦某个字符次数超过 2，就右移左指针收缩窗口，直到该字符重新合法。

用哈希表 cnt 维护窗口内各字符的出现次数。由于新字符是右指针刚加入的、唯一可能出现超限的就是 s[right] 本身，所以内层只用 while cnt[s[right]] > 2 这一个条件即可触发收缩，其余字符天然不可能超限。

算法步骤#

初始化 ans = left = 0，cnt 为空字典。
枚举 right，把 s[right] 计数加一。
while cnt[s[right]] > 2：把 s[left] 计数减一，left += 1（收缩直到刚加入的字符不超限）。
用当前窗口长 right - left + 1 更新 ans。
返回 ans。

逐步举例#

以 s = "bcbbbcba" 为例（期望答案 4）：

right	字符	入窗后计数	收缩动作	窗口	长度	ans
0	b	b:1	—	[0,0]=“b”	1	1
1	c	b:1,c:1	—	[0,1]=“bc”	2	2
2	b	b:2,c:1	—	[0,2]=“bcb”	3	3
3	b	b:3,c:1	左移，b:2	[1,3]=“bcb”	3	3
4	b	b:3→2	左移两次	[3,4]=“bb”	2	3
5	c	b:2,c:1	—	[3,5]=“bbc”	3	3
6	b	b:3→2	左移一次	[4,6]=“bcb”	3	3
7	a	含 a,b:2,c:1	—	[4,7]=“bcba”	4	4

遍历结束，最长合法子串长度为 4。

题解#

1
class Solution:
2
    def maximumLengthSubstring(self, s: str) -> int:
3
        ans = left = 0
4
        cnt = {}
5
        for right, ch in enumerate(s):
6
            cnt[ch] = cnt.get(ch, 0) + 1
7
            while cnt[ch] > 2:
8
                cnt[s[left]] -= 1
9
                left += 1
10
            ans = max(ans, right - left + 1)
11
        return ans

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

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

10
    def test_example1(self):
11
        self.assertEqual(self.solution.maximumLengthSubstring("bcbbbcba"), 4)
12

13
    def test_example2(self):
14
        self.assertEqual(self.solution.maximumLengthSubstring("aaaa"), 2)
15

16
    def test_all_unique(self):
17
        self.assertEqual(self.solution.maximumLengthSubstring("abcdef"), 6)
18

19
    def test_single_char(self):
20
        self.assertEqual(self.solution.maximumLengthSubstring("a"), 1)
21

22
    def test_two_chars(self):
23
        self.assertEqual(self.solution.maximumLengthSubstring("ab"), 2)
24

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

复杂度分析#

时间复杂度：O(n)，左右指针各遍历一次序列
空间复杂度：O(|Σ|)，Σ 为字符集大小（本题仅 26 个小写字母可视为 O(1)）