ধরুন '0' এবং '1'-এর একটি স্ট্রিং দেওয়া আছে। সেই স্ট্রিংটি একঘেয়ে ক্রমবর্ধমান হবে যদি এতে '0' এর কিছু সংখ্যা থাকে (সম্ভবত 0), তারপরে '1' এর কিছু সংখ্যা (এছাড়াও সম্ভবত 0।)। আমাদের '0' এবং '1'-এর একটি স্ট্রিং S আছে, এবং আমরা '0' থেকে '1' বা '1' থেকে '0' ফ্লিপ করতে পারি। S একঘেয়ে বাড়ানোর জন্য সর্বনিম্ন সংখ্যক ফ্লিপ খুঁজুন। তাই ইনপুট যদি "010110" এর মত হয়, তাহলে আউটপুট হবে 2। ফ্লিপ করে আমরা "011111" বা "000111" পেতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=S এর আকার, flipCount সেট করুন :=0, oneCount :=0
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি S[i] 0 হয়, তাহলে
-
যদি oneCount =0 হয়, তাহলে পরবর্তী পুনরাবৃত্তিতে চলে যান
-
flipCount 1 দ্বারা বাড়ান
-
-
অন্যথায় onecount 1 দ্বারা বাড়ান
-
যদি oneCount
-
-
রিটার্ন flipCount
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
};
main(){
Solution ob;
cout << (ob.minFlipsMonoIncr("010110"));
} ইনপুট
"010110"
আউটপুট
2
