Description
給定二進位字串
s，可以執行兩種操作：
- Type-1: 移除最左邊的字元並加到最右邊
- Type-2: 翻轉任一位元（0->1 或 1->0）
回傳使字串變成交替字串（“010101…” 或 “101010…"）所需的最少 Type-2 操作次數（Type-1 可以做任意次）。
Example:
Input: s = “111000” Output: 2（先做 Type-1 兩次得到 “100011”，再翻轉兩位得到 “101010”）
Intuition#
核心思路：把字串複製一份接在後面模擬循環旋轉，然後用固定大小為 n 的滑動視窗，計算每個旋轉版本與兩種交替模式的差異數。
- Type-1 操作就是循環旋轉，把
s拼接成s + s後，任何長度 n 的子字串就是一種旋轉結果 - 目標只有兩種：
"010101..."和"101010..." - 對每個旋轉版本，計算需要幾次 Type-2 翻轉才能匹配目標
Approaches#
1: 模擬所有旋轉#
- 概念: 嘗試每種旋轉，對每種旋轉計算與兩個目標的差異數
- 時間複雜度:
O(n²)- n 種旋轉各掃描 n 個字元 - 空間複雜度:
O(n)- 旋轉後的字串
模擬程式碼
class Solution {
fun minFlips(s: String): Int {
val n = s.length
var result = n
for (rot in 0 until n) {
val rotated = s.substring(rot) + s.substring(0, rot)
var diff0 = 0 // 與 "0101..." 的差異
var diff1 = 0 // 與 "1010..." 的差異
for (i in rotated.indices) {
val expected0 = if (i % 2 == 0) '0' else '1'
if (rotated[i] != expected0) diff0++
else diff1++
}
result = minOf(result, diff0, diff1)
}
return result
}
}⭐2: 字串拼接 + Fixed Sliding Window#
- 概念: 將
s + s作為基礎，預計算每個位置與兩種交替模式的差異，用大小為 n 的滑動視窗維護差異計數 - 時間複雜度:
O(n)- 一次遍歷拼接後的字串 - 空間複雜度:
O(n)- 拼接字串
class Solution {
fun minFlips(s: String): Int {
val n = s.length
val doubled = s + s
var diff0 = 0 // 與 "010101..." 不同的位數
var diff1 = 0 // 與 "101010..." 不同的位數
var result = n
for (i in doubled.indices) {
// 位置 i 對應交替模式的期望值
val expected0 = if (i % 2 == 0) '0' else '1'
if (doubled[i] != expected0) diff0++
else diff1++ // expected1 與 expected0 互補
// 移除左邊離開視窗的字元
if (i >= n) {
val leftExpected0 = if ((i - n) % 2 == 0) '0' else '1'
if (doubled[i - n] != leftExpected0) diff0--
else diff1--
}
// 視窗大小達到 n 時更新結果
if (i >= n - 1) {
result = minOf(result, diff0, diff1)
}
}
return result
}
}交替模式的判斷用
i % 2（全域位置），不是視窗內的相對位置。因為s + s中拼接後位置的奇偶性自然對應正確的交替模式。
🔑 Takeaways#
- Pattern: 字串拼接模擬循環 + 固定大小滑動視窗
- 關鍵技巧:
s + s是處理循環旋轉問題的標準技巧；同時追蹤兩種目標模式的差異數，避免重複計算