সমস্যা বিবরণ
একটি বাইনারি স্ট্রিং দেওয়া আছে, এর থেকে সাবস্ট্রিং "010" মুছে ফেলার ন্যূনতম ধাপ গণনা করতে হবে।
উদাহরণ
ইনপুট স্ট্রিং "010010" হলে ২টি ধাপ দরকার:
- প্রথম 0 কে 1 এ রূপান্তর। এখন স্ট্রিং: 110010
- শেষ 0 কে 1 এ রূপান্তর। ফাইনাল স্ট্রিং: 110011
অ্যালগরিদম
1. স্ট্রিংকে ইনডেক্স 0 থেকে n-2 পর্যন্ত ইটারেট করুন 2. যদি বাইনারি স্ট্রিং-এ लगাতার তিনটি ক্যারেক্টার '0', '1', '0' পাওয়া যায়, তবে যেকোনো একটি ক্যারেক্টার পরিবর্তন করুন লুপ কাউন্টার ২ বাড়ান
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) {
int cnt = 0;
for (int i = 0; i < str.length() - 2; ++i) {
if (str[i] == '0' && str[i + 1] == '1' && str[i+ 2] == '0') {
++cnt;
i += 2;
}
}
return cnt;
}
int main() {
string str = "010010";
cout << "Minimum required steps = " << getMinSteps(str) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum required steps = 2
