1888. Minimum Number of Flips to Make the Binary String Alternating

📘 題目敘述

給你一個二元字串 s。你可以對字串進行任意次、任意順序的以下兩種操作：

Type-1：移除字串 s 開頭的字元，並把它接到字串尾端
Type-2：選擇字串中的任意一個字元並翻轉它，也就是如果它是 '0' 就變成 '1'，如果它是 '1' 就變成 '0'

請回傳最少需要做幾次 Type-2 操作，才能讓 s 變成 alternating。

如果一個字串中沒有任何兩個相鄰字元相同，就稱這個字串是 alternating。

例如，"010" 和 "1010" 是 alternating，而 "0100" 不是。

條件限制

1 <= s.length <= 10^5
s[i] 只會是 '0' 或 '1'

🧠 解題思路

這題可以做兩種操作，但真正麻煩的其實是 Type-1，也就是把前面一個字元丟到後面。

我一開始的想法是：

先先算目前這個字串如果要變成交錯字串，需要幾次 flip
然後每次把最前面那一位想成「丟到最後面」
在這個過程中，持續更新目前要變成 alternating 的代價

這題的關鍵觀察是：

alternating 字串只可能有兩種型態
- 010101...
- 101010...

所以只要知道目前字串和這兩種型態各差多少位，就能知道最少要翻幾次。

我這份程式用兩個變數：

c0：目前字串和「從 0 開始的交錯字串」相比，有幾個位置不一樣
c1：目前字串和「從 1 開始的交錯字串」相比，有幾個位置不一樣

先掃一遍原字串，把這兩個值算出來。

接著分成兩種情況：

如果字串長度是偶數
- 那不管怎麼把前面丟到後面，奇偶位置的結構不會真的改變本質
- 所以旋轉後的答案其實不會比原本更特別，直接回傳 min(c0, c1) 就好
如果字串長度是奇數
- 每做一次 Type-1，整個字串的奇偶位置角色都會對調
- 原本對 0101... 算錯的位置，旋轉後會變成對 1010... 那邊去
- 所以可以在每次移動一個字元時，直接用 O(1) 更新 c0 和 c1

也就是說，這題雖然表面上像是在試很多輪旋轉，但實際上不用真的建新字串，只要維護這兩個 mismatch 計數就夠了。

所有變數

c0：目前字串相對於 010101... 這種型態的錯誤數量
c1：目前字串相對於 101010... 這種型態的錯誤數量
n：字串長度
ans：目前所有旋轉情況中的最小 flip 次數

🪜 主要流程步驟

1. 先掃一次字串，算出原本字串對兩種 alternating 型態的差異數

我先把字串和兩種可能的交錯型態比較：

一種是從 0 開始：010101...
一種是從 1 開始：101010...

程式中是這樣判斷的：

if (s[i] - '0' == i % 2) {
    c0++;
} else {
    c1++;
}

這裡的意思是：

如果 s[i] 剛好等於 i % 2
- 代表它符合 010101... 這個型態
- 那它對另一種 101010... 就一定是不符合的
否則就反過來

所以掃完整串之後：

c0 代表符合 0101... 的位置數
c1 代表符合 1010... 的位置數

而最後真正需要 flip 的次數，其實就是看哪一種型態比較接近。

在這份寫法裡，兩個值在旋轉更新時會互相調整，所以後面直接取 min(c0, c1) 來更新答案。

2. 如果字串長度是偶數，直接回傳答案

if (n % 2 == 0) {
    return min(c0, c1);
}

這一步是這題最重要的觀察之一。

因為當字串長度是偶數時，把最前面一個字元丟到最後面，相當於整體平移一格，但 alternating 的奇偶結構不會產生「兩種型態互換」那種效果。

所以：

原本最接近哪一種 alternating 型態
旋轉之後本質上還是同樣的情況

因此偶數長度不需要模擬每次旋轉，直接回傳原本的最小 flip 數就可以。

3. 如果字串長度是奇數，就要模擬每次把最前面一位丟到最後面

如果 n 是奇數，每次做一次 Type-1，整串字元的奇偶位置都會翻轉。

這就是為什麼奇數長度要特別處理。

先把原本答案設成：

int ans = min(c0, c1);

然後對每個位置 i，把 s[i] 想成從前面被移到後面。

4. 更新 c0 和 c1，表示這次旋轉後的新狀態

程式裡這段是核心：

if (s[i] - '0' == i % 2) {
    c1++;
    c0--;
} else {
    c0++;
    c1--;
}

這段的意思是：

當 s[i] 從前面移到最後面後，因為字串長度是奇數，所以其他字元的奇偶角色全部翻轉。

因此原本對某種型態「符合」的字元，旋轉後會變成對另一種型態去計算。

所以這裡不是重新掃一遍整串，而是直接把這一位對 c0、c1 的貢獻做轉換：

如果這一位原本是符合 i % 2 的那邊
- 旋轉後它的角色改變，就要從原本那邊扣掉，補到另一邊
否則就反過來

這樣每次旋轉都只要 O(1) 更新。

5. 每次旋轉後都更新答案

ans = min(ans, min(c0, c1));

因為每旋轉一次，都得到一個新的字串排列。

對這個排列：

變成 0101... 需要的 flip 數
變成 1010... 需要的 flip 數

兩者取較小值，就是這次旋轉的最少 flip 次數。

再和全域答案 ans 比較，留下最小值。

6. 全部旋轉情況看完後回傳答案

當 i 從 0 到 n - 1 全部跑完，代表所有可能的 Type-1 起點都考慮過了。

最後回傳 ans，就是所有旋轉方式中，最少需要的 Type-2 次數。

⏱️ 複雜度

時間複雜度：O(n)
先掃一次字串，奇數長度時再模擬一輪旋轉更新，總共仍是線性時間。
空間複雜度：O(1)
只用了幾個整數變數來記錄計數與答案。

💻 程式碼實作

class Solution {
public:
    int minFlips(string s) {
        int c0 = 0, c1 = 0; // c0是0開始
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] - '0' == i % 2) {
                c0++;
            } else {
                c1++;
            }
        }
        if (n % 2 == 0) {
            return min(c0, c1);
        }
        int ans = min(c0, c1);
        for (int i = 0; i < n; i++) {
            if (s[i] - '0' == i % 2) {
                c1++;
                c0--;
            } else {
                c0++;
                c1--;
            }
            ans = min(ans, min(c0, c1));
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/