題目鏈接

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 次）。