难度: Easy
给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。
示例 1：
输入： s = "bcbbbcba"
输出： 4
解释：
以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。
示例 2：
输入： s = "aaaa"
输出： 2
解释：
以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。
提示：
2 <= s.length <= 100s仅由小写英文字母组成。
Submission
运行时间: 35 ms
内存: 16.0 MB
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
# 哈希表记录字符出现次数
char_count = {}
# 最大子字符串长度
max_len = 0
# 左指针
left = 0
for right in range(len(s)):
# 更新字符出现次数
char_count[s[right]] = char_count.get(s[right], 0) + 1
# 如果某个字符的出现次数超过2次，移动左指针直到该字符的出现次数恢复为2以下
while char_count[s[right]] > 2:
char_count[s[left]] -= 1
left += 1
# 更新最大子字符串长度
max_len = max(max_len, right - left + 1)
return max_len
Explain
该题解采用了滑动窗口的方法。首先定义一个哈希表来记录窗口内各字符的出现次数，以及一个变量来记录最大子字符串的长度。通过一个右指针遍历字符串，并在哈希表中更新该字符的出现次数。如果字符的出现次数超过2，即不满足题目要求，此时通过移动左指针减少该字符的计数，直到该字符的出现次数不超过2。在每次右指针移动后，更新最大长度。这样，当右指针遍历完整个字符串后，可以得到满足条件的最长子字符串的长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
char_count = {} # 哈希表记录字符出现次数
max_len = 0 # 最大子字符串长度
left = 0 # 左指针
for right in range(len(s)):
char_count[s[right]] = char_count.get(s[right], 0) + 1 # 更新字符出现次数
# 如果某个字符的出现次数超过2次，移动左指针直到该字符的出现次数恢复为2以下
while char_count[s[right]] > 2:
char_count[s[left]] -= 1
left += 1
# 更新最大子字符串长度
max_len = max(max_len, right - left + 1)
return max_len
Explore
在滑动窗口方法中，使用哈希表来跟踪窗口内每个字符的计数是处理字符计数的有效方式。每当右指针向右移动时，对当前字符的计数增加1；如果字符计数超过2，左指针向右移动，同时对移出窗口的字符的计数减少1。这种方式确保了每个字符的计数操作仅涉及常数时间复杂度O(1)，从而使整体循环的效率得到保证。
在此问题中，哈希表用于存储和跟踪窗口内每个字符的出现次数。选择哈希表是因为它提供了快速的插入、删除和查找操作，每个操作平均时间复杂度为O(1)。这使得在滑动窗口算法中，对字符计数的更新和查询可以迅速进行，从而有效地维护和调整窗口大小以满足题目的要求。
当字符的出现次数超过2次时，这意味着窗口内该字符的数量已不符合题目要求。移动左指针（减少窗口的左边界）是解决这一问题的直接方法，因为它可以减少这个超限字符的计数，直至其符合要求。不需要考虑其他字符的原因是，其他字符的出现次数在此时都符合要求（即不超过2次），因此只需调整超过限制的那个字符。这种策略简化了问题的处理，确保了算法的效率。