'০' এবং '১' দিয়ে গঠিত একটি স্ট্রিং দেওয়া আছে। স্ট্রিংটি monotonic increasing হবে যদি এটি কিছু সংখ্যক '০' (সম্ভবত ০), তারপর কিছু সংখ্যক '১' (সম্ভবত ০) দিয়ে গঠিত হয়। একটি '০' এবং '১' দিয়ে গঠিত স্ট্রিং S আছে, এবং আমরা যেকোনো '০'-কে '১' বা '১'-কে '০' ফ্লিপ করতে পারি। S-কে monotone increasing করার জন্য ন্যূনতম ফ্লিপ সংখ্যা খুঁজে বের করতে হবে। ইনপুট "010110" হলে আউটপুট ২। ফ্লিপ করলে "011111" বা "000111" পাওয়া যায়।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := S.size(), flipCount := 0, oneCount := 0
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
যদি S[i] == '0' হয়, তবে
যদি oneCount == 0 হয়, পরবর্তী ইটারেশনে যান
flipCount++ করুন
অন্যথায় oneCount++ করুন
যদি oneCount < flipCount হয়, flipCount := 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
