2025-11-08：不相交子字符串的最大數量。用go語言，給定字符串 word，求最多能從中取出多少個互不重疊的連續片段（即子串），要求每個片段長度不少於 4 且第一個字符和最後一個字符相同。返回這個最大數量。
1 <= word.length <= 200000。
word 僅由小寫英文字母組成。
輸入： word = “abcdeafdef”。
輸出： 2。
解釋：
兩個子字符串是 “abcdea” 和 “fdef”。
題目來自力扣3557。
算法分步解析
該算法使用貪心策略和位運算優化來高效解決問題。以下是詳細的分步過程：
1. 初始化階段
- 定義
ans變量統計有效子串數量，初始為0。 - 定義
seen變量作為位掩碼（32位整數），初始為0，用於記錄最近出現過的字符（小寫字母映射到0-25位）。 - 從索引
i = 3開始遍歷字符串（因為子串長度至少為4，需檢查word[i-3]到word[i]的範圍）。
2. 遍歷與字符記錄
- 對於每個位置
i（從第4個字符開始）：
- 更新位掩碼：將
word[i-3]對應的位設為1（seen |= 1 << (word[i-3] - 'a')）。這一步記錄當前窗口前第3個字符的出現狀態。 - 檢查終止條件：判斷
word[i]是否在seen中出現過（seen >> (word[i] - 'a') & 1 > 0）。若為真，説明存在以word[i]結尾且長度≥4的子串，其首尾字符相同。
- 例如，當
i=5時，若word[5]與之前某個word[j]（j≤2）相同，則子串word[j:5+1]滿足條件。
3. 貪心選擇與跳躍
- 一旦檢測到有效子串（首尾字符相同）：
- 計數器
ans加1。 - 重置
seen為0，清空歷史字符記錄。 - 跳躍指針：將索引
i增加3（i += 3），確保下一個子串不會與當前子串重疊。跳躍後，循環本身的i++會使下一次檢查從i+4開始，避免重複利用字符。
4. 終止與返回
- 遍歷完成後，返回
ans作為最大不相交子串數量。 - 示例
word = "abcdeafdef"：
- 檢測到
"abcdea"（首尾'a'相同）後計數為1，跳過中間字符。 - 繼續檢測到
"fdef"（首尾'f'相同）後計數為2。
時間與空間複雜度
- 時間複雜度：O(n)。
每個字符最多被訪問一次（跳躍機制避免重複掃描），位運算和判斷操作均為O(1)。 - 空間複雜度：O(1)。
僅使用固定大小的變量（ans,seen,i），與輸入規模無關。
關鍵設計思想
- 貪心選擇：優先選擇最短的有效子串（長度剛好為4時最優），以最大化子串數量。
- 位運算優化：用
seen的比特位替代哈希表，快速查詢字符出現歷史。 - 跳躍式遍歷：通過
i += 3避免重疊，減少冗餘檢查。
此算法高效利用了問題約束（字符集小、子串長度固定），實現了線性時間與常數空間的最優解。
Go完整代碼如下：
package main
import (
"fmt"
)
func maxSubstrings(word string) (ans int) {
seen := 0
for i := 3; i < len(word); i++ {
seen |= 1 << (word[i-3] - 'a')
if seen>>(word[i]-'a')&1 > 0 { // 再次遇到 word[i]
ans++
seen = 0
i += 3
}
}
return
}
func main() {
word := "abcdeafdef"
result := maxSubstrings(word)
fmt.Println(result)
}
Python完整代碼如下：
# -*-coding:utf-8-*-
def max_substrings(word: str) -> int:
ans = 0
seen = 0
i = 3
while i < len(word):
# 將前3個位置的字符記錄到seen中
seen |= 1 << (ord(word[i - 3]) - ord('a'))
# 檢查當前字符是否在seen中出現過
if (seen >> (ord(word[i]) - ord('a'))) & 1 > 0:
ans += 1
seen = 0
i += 3 # 跳過3個字符
i += 1
return ans
# 測試代碼
if __name__ == "__main__":
word = "abcdeafdef"
result = max_substrings(word)
print(result)
C++完整代碼如下：
#include <iostream>
#include <string>
using namespace std;
int maxSubstrings(string word) {
int ans = 0;
int seen = 0;
for (int i = 3; i < word.length(); i++) {
seen |= 1 << (word[i - 3] - 'a');
if ((seen >> (word[i] - 'a')) & 1) { // 再次遇到 word[i]
ans++;
seen = 0;
i += 3;
}
}
return ans;
}
int main() {
string word = "abcdeafdef";
int result = maxSubstrings(word);
cout << result << endl;
return 0;
}
