0926. Flip String to Monotone Increasing (Medium)

926. Flip String to Monotone Increasing (Easy)

Question

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

Return the minimum number of flips to make S monotone increasing.

Example 1

1
2
3

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2

1
2
3

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3

1
2
3

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

分析/解題

一個只含'0’和'1’的字串在以下的狀況成立時會被視為單調遞增 ：
數個'0’作為開頭(也可能是0個)，其後接著數個'1’作為開頭(也可能是0個)。
(簡單說就是0後面接1就對了，也可以全0或全1)
給定一個字串s ，且可以將當中任意的'0’翻轉成'1’，
也可以將任意的'1’翻轉成'0’，
試求要將s經過翻轉操作成為單調遞增 的狀態所需的最小翻轉次數 。

這題其實某種程度隱含了一點動態規劃的概念在內，
但相對而言算是較簡單的。

我們先思考根據單調遞增特性，由於這個特性，
注定了一旦在某個點變為1，其後的每個單位也必須要是1 才可以。
若將最後的結果分成兩個狀況的話，事情會變比較簡單：

1. 全部都是0
2. 前面0後面1(含全部都是1)

考慮做到第i位時，要保持單調遞增所需翻轉的次數:
a. 如果第i位是0，對狀況1來說，不需額外作任何事情即可保持
b. 如果第i位是1，對狀況1來說，要將第i位翻轉為0(翻轉次數+1)
c. 如果第i位是0，對狀況2來說，要將第i位翻轉為1(翻轉次數+1)
d.如果第i位是1，對狀況2來說，相當於從第i-1位時選擇狀況1/狀況2均可

若我們將上面的狀況1所需的翻轉次數叫做f0，
狀況2的所需次數叫做f1的話，
上面的a/c就是第i位碰到'0’的狀況 ，此時從第i-1位的f0/f1 更新到第i位 時，
新的f0不需改變 ，但f1必須遞增 ；
b/d就是碰到'1’的狀況 ，更新時新的f1要取原先的f0, f1中較小的値 ，
且f0必須要遞增 。

一開始什麼都還沒做，所以我們可以定f0, f1均為0 ，
接下來從頭到尾依照碰到的字元進行操作。

最終，答案只要取f0/f1中較小值 即可。

依此寫成程式碼：
Java的部分可以利用for each的語法蜜糖來取出單個char，
(記得S要先轉成char array)
且需要留意f0的遞增要在取完f1之後 (不然值會錯)。

Java

Python的部分亦同，記得只有+=沒有++這種東西XD

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，需遍歷整個String的長度，但記錄用輔助變數只需常數單位)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~