Flip String to Monotone Increasing ใน C++

คำอธิบายปัญหา

สตริง '0' และ '1' จะเป็น monotone increasing ถ้าประกอบด้วย '0' บางส่วนตามด้วย '1' บางส่วน (อาจว่างได้) สามารถพลิก '0'↔'1' ได้ ต้องการจำนวนการพลิกน้อยที่สุด

ตัวอย่าง: "010110" → 2 (กลายเป็น "011111" หรือ "000111")

วิธีแก้ปัญหา (One Pass Greedy)

1. นับ oneCount = จำนวน '1' ที่ผ่านมา
2. flipCount = จำนวนการพลิกที่ต้องทำจนถึงตำแหน่งปัจจุบัน
3. เมื่อเจอ '0': ถ้ามี '1' ก่อนหน้า (oneCount>0) ต้องพลิก '0' นี้เป็น '1' (flipCount++)
4. เมื่อเจอ '1': oneCount++
5. ปรับ flipCount = min(flipCount, oneCount) (เลือกพลิก '1' ก่อนหน้าเป็น '0' แทน)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int flipCount = 0, oneCount = 0;
        for(char c : S) {
            if(c == '0') {
                if(oneCount > 0) flipCount++;
            } else {
                oneCount++;
            }
            flipCount = min(flipCount, oneCount);
        }
        return flipCount;
    }
};

int main() {
    Solution ob;
    cout << ob.minFlipsMonoIncr("010110");
    return 0;
}

อินพุต

"010110"

เอาต์พุต

2