題目描述:給一個只含 'a'、'b'、'c' 的字串 s 和整數 k,每次操作可從最左或最右取一個字元,目標是讓每種字元都取到至少 k 個,回傳最少操作次數,若不可能則回傳 -1。
解題思路:問題的關鍵洞察是逆向思維:「從左端和右端取字元」等價於「保留中間一段連續子字串不取」。若我們選擇保留中間一段 [left, right] 不動,那麼取走的就是左端 [0, left-1] 和右端 [right+1, n-1] 兩段。
因此,問題轉化為:找最長的中間子字串(滑動視窗),使得被取走的左端 + 右端部分,每種字元 'a'、'b'、'c' 的數量都 ≥ k。答案即為 n - 最長中間段長度。
具體做法:先計算整個字串中 'a'、'b'、'c' 的總頻率 total[]。維護一個可伸縮視窗 [left, right],視窗內各字元的計數為 window[]。當加入右端字元後,若「已被取走的數量」(即 total[c] - window[c])對某字元 c 小於 k,則從左端縮小視窗直到條件恢復。若整個字串的某種字元總數 < k,最終答案為 -1。
時間複雜度:O(n) — 左右指標各最多移動 n 步;計算總頻率也是 O(n)。
空間複雜度:O(1) — 僅使用固定大小(3 個元素)的計數陣列,不隨輸入規模增長。
1. Count total frequency of 'a', 'b', 'c' in s (total[])
2. If total[0]<k or total[1]<k or total[2]<k: return -1
3. If k==0: return 0
4. Initialize window[3]={0,0,0}, left=0, maxSkip=0
5. For right from 0 to n-1:
a. window[s[right]-'a']++
b. While (total[c]-window[c] < k) for any c in {0,1,2}:
- window[s[left]-'a']--
- left++
c. maxSkip = max(maxSkip, right-left+1)
6. Return n - maxSkip前綴和 + 二分搜尋 O(n log n):預先建立 'a'、'b'、'c' 的前綴計數陣列。對每個可能的「左端取走長度」用二分搜尋找出最小的「右端取走長度」,使三種字元都滿足需求。時間 O(n log n),空間 O(n),不如滑動視窗簡潔。
暴力列舉 O(n²):枚舉所有可能的「左端取 i 個、右端取 j 個」的組合(i + j 最小化),對每個組合檢查是否滿足 k 的需求。時間 O(n²),空間 O(1)。在 n 達 10⁵ 時會超時。
雙指標(等價寫法)O(n):等同滑動視窗,但視角改為直接維護「已取走的左段長度 l 和右段長度 r」,不斷嘗試縮短總長度 l + r。邏輯相同但程式碼稍繁瑣。
total[] 和 window[] 改為大小 26 的陣列,條件檢查需遍歷全部 26 種字元)