C++ में मोनोटोन बढ़ती स्ट्रिंग में फ्लिप (Flip String to Monotone Increasing)

मान लीजिए '0's और '1's की एक स्ट्रिंग दी गई है। वह स्ट्रिंग मोनोटोनिकली बढ़ती (monotone increasing) होगी यदि इसमें कुछ संख्या में '0's (संभवतः 0), उसके बाद कुछ संख्या में '1's (संभावतः 0) हों। हमारे पास '0's और '1's की एक स्ट्रिंग S है, और हम किसी भी '0' को '1' में या '1' को '0' में फ्लिप कर सकते हैं। S को मोनोटोन बढ़ता बनाने के लिए न्यूनतम फ्लिप्स की संख्या खोजें।

उदाहरण के लिए, यदि इनपुट "010110" है, तो आउटपुट 2 होगा। फ्लिप करके हम "011111" या "000111" प्राप्त कर सकते हैं।

समाधान दृष्टिकोण

1. n := S का आकार, flipCount := 0, oneCount := 0

2. i को 0 से n-1 तक:

3. यदि S[i] == '0': oneCount > 0 होने पर flipCount++

4. अन्यथा oneCount++

5. यदि oneCount < flipCount तो flipCount = oneCount

6. flipCount लौटाएं

C++ कार्यान्वयन

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

class Solution { 
public: 
    int minFlipsMonoIncr(string S) { 
        int n = S.size(); 
        int flipCount = 0; 
        int oneCount = 0; 
        for(int i = 0; i < n; i++){ 
            if(S[i] == '0'){ 
                if(oneCount == 0) continue; 
                flipCount++; 
            } else oneCount++; 
            if(oneCount < flipCount) flipCount = oneCount; 
        } 
        return flipCount; 
    } 
}; 

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

इनपुट

"010110"

आउटपुट

2