题目链接

https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/

题目描述

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

示例

• 输入：s = "aabba"
  • 输出：5
  • 解释：子字符串 "aabba" 中每个字符（a 和 b）最多出现两次，且长度为 5。
• 输入：s = "aaaa"
  • 输出：2
  • 解释：最长子字符串为 "aa"，每个字符最多出现两次。

解法分析：滑动窗口 + 数组计数

核心思路

本题采用滑动窗口算法，通过左右指针维护一个有效区间，确保区间内每个字符的出现次数不超过 2 次。同时，利用长度固定的数组记录字符出现的频率，实现高效的计数与判断。

代码实现

class Solution:def maximumLengthSubstring(self, s: str) -> int:# 使用长度26的数组记录小写字母出现次数（假设输入仅包含小写字母）count = [0] * 26ans = left = 0for right in range(len(s)):# 计算当前字符的索引（a=0, b=1,...z=25）idx = ord(s[right]) - ord('a')count[idx] += 1  # 右指针字符计数+1# 当字符出现次数>2时，移动左指针收缩窗口while count[idx] > 2:left_idx = ord(s[left]) - ord('a')count[left_idx] -= 1  # 左指针字符计数-1left += 1            # 左指针右移# 更新最大窗口长度ans = max(ans, right - left + 1)return ans

关键逻辑解析

1. 初始化：

   • count：长度为 26 的数组，用于记录小写字母的出现次数，假设输入仅包含小写字母。数组下标 0 对应字符 a，1 对应 b，以此类推。
   • ans：记录满足条件的最长子字符串长度，初始值为 0。
   • left：滑动窗口的左指针，初始值为 0。

2. 右指针扩展：

   • 使用 right 从左到右遍历字符串 s。
   • 通过 ord(s[right]) - ord('a') 将字符转换为数组索引，对 count 数组中对应位置的计数加 1，表示当前字符出现次数增加。

3. 左指针收缩：

   • 当 count[idx] > 2 时，说明当前字符在窗口内出现次数超过 2 次，需要收缩窗口。
   • 通过 ord(s[left]) - ord('a') 计算左指针指向字符的索引，将其在 count 数组中的计数减 1。
   • 左指针 left 右移一位，缩小窗口范围，直到当前字符出现次数不超过 2 次。

4. 更新结果：

   • 每次循环中，计算当前窗口的长度 right - left + 1，并与 ans 比较，取较大值更新 ans。
   • 最终返回 ans，即满足条件的最长子字符串长度。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 s 的长度。左右指针最多各遍历字符串一次，每个字符最多被处理两次。
• 空间复杂度：$O(1)$，数组 count 的长度固定为 26，与输入字符串的长度无关。

优化点与注意事项

1. 数组替代字典：使用固定长度的数组替代字典记录字符频率，避免哈希计算开销，在字符集固定（如小写字母）的场景下更高效。
2. 字符集假设：当前代码假设输入仅包含小写字母，若字符集扩展（如包含大写字母、数字等），需要扩展数组长度或改用字典存储。
3. 边界条件：代码默认输入字符串非空，题目保证 s.length ≥ 2，因此无需额外处理空字符串。

总结

本解法通过滑动窗口和数组计数的结合，在 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度内高效解决问题。其核心在于利用双指针动态维护有效区间，并通过数组快速判断字符出现频率。该思路可作为处理字符频率约束类问题的通用模板，适用于更多变种题型（如每个字符最多出现 k 次）。