MediumRating 2006
1888. Minimum Number of Flips to Make the Binary String Alternating
stringdynamic-programmingsliding-window
解題說明
Minimum Number of Flips to Make the Binary String Alternating
題目描述：
給定一個二進位字串 s，可以執行兩種操作：
- 操作 1（type-1）：將字串最左邊的字元移到最右邊（循環左移）。
- 操作 2（type-2）：翻轉字串中任意一個字元（0 變 1 或 1 變 0）。
求使字串變成交替字串（"010101..." 或 "101010..."）的最少操作 2 次數（操作 1 可以用任意次）。
解題思路：
- 將字串複製一份接在後面：
s + s，長度為 2n。這樣所有循環左移的結果都是s+s的長度為 n 的子串。 - 對
s+s的每個位置 i，計算它與兩種交替模式（"0101..." 和 "1010..."）不匹配的情況。 - 用長度為 n 的滑動窗口在
s+s上滑動，維護窗口內兩種模式各需要多少次翻轉（type-2 操作），取最小值。
C++ 解法
複雜度分析
時間複雜度：O(n) — 在長度 2n 的字串上進行一次滑動窗口遍歷。
空間複雜度：O(n) — 建立了 doubled 字串。可以用取模優化到 O(1)。
虛擬碼
1. Create doubled = s + s 2. Initialize count0 = 0, count1 = 0 (mismatches for two alternating patterns) 3. Initialize ans = n 4. For each index i in doubled: a. Check if doubled[i] mismatches pattern "010101..." at position i → update count0 b. Check if doubled[i] mismatches pattern "101010..." at position i → update count1 c. If i >= n, remove the contribution of index (i - n) from count0 and count1 d. If i >= n - 1 (window is full): ans = min(ans, min(count0, count1)) 5. Return ans
其他解法
枚舉所有旋轉 O(n²)：對每種循環左移，逐一計算翻轉次數。簡單但 n 大時超時。
O(1) 空間滑動窗口：不建立 doubled 字串，用 i % n 取模存取原字串。省去 O(n) 空間但程式碼可讀性略降。
延伸思考
- 如果只允許操作 1（循環左移）而不能翻轉，能否一定得到交替字串？什麼情況下可以？
- 如果操作 1 改為任意旋轉（不限於左移一位），答案會不同嗎？
- 如果目標不是交替字串而是其他模式（例如 "001001001..."），如何推廣此方法？