C++-এ বাইনারি স্ট্রিংকে "ab" মুক্ত করার জন্য অপারেশন সংখ্যা গণনা

আমাদের একটি স্ট্রিং দেওয়া আছে যেটিতে "ab" প্যাটার্ন থাকতে পারে। লক্ষ্য হল স্ট্রিং থেকে "ab" সম্পূর্ণ সরিয়ে ফেলা বা "ab"-মুক্ত করা। প্রতিটি অপারেশনে "ab"-কে "bba"-তে রিপ্লেস করা হয়। এই অপারেশন কতবার করতে হবে তা গণনা করতে হবে।

উদাহরণ

ইনপুট: str = "ababaa"

আউটপুট: ৪

ব্যাখ্যা:

"ababaa" → "bbaabaa" (1)
"bbaabaa" → "bbabbaaa" (2)
"bbabbaaa" → "bbabbbaaa" (3)
"bbabbbaaa" → "ab"-মুক্ত (4)

ইনপুট: str = "abaa"

আউটপুট: ১

অ্যালগরিদম

স্ট্রিংয়ের শেষ থেকে শুরু করুন। যদি 'a' পাওয়া যায় তবে অপারেশন সংখ্যা বাড়ে এবং 'b' এর সংখ্যা দ্বিগুণ হয়। যদি 'b' পাওয়া যায় তবে শুধু 'b' কাউন্ট বাড়ে। এটি O(n) সময়ে সমাধান করা যায়।

স্ট্রিং এবং এর দৈর্ঘ্য ফাংশনে পাস করুন।
ক্যারেক্টার অ্যারে-তে কপি করুন।
উল্টা দিক থেকে ট্রাভার্স করুন (i=0 থেকে length-1)।
যদি arr[len-i-1] == 'a' হয়: count += total; total *= 2।
অন্যথায় (যদি 'b' হয়): total++।
শেষে count ফেরত দিন।

C++ বাস্তবায়ন

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

int operations_ab_free(string str, int len) {
    int count = 0;
    char arr[len + 1];
    strcpy(arr, str.c_str());
    int total = 0;
    
    for (int i = 0; i < len; i++) {
        if (arr[len - i - 1] == 'a') {
            count += total;
            total *= 2;
        } else {
            total++;
        }
    }
    return count;
}

int main() {
    string str = "ababaa";
    int length = str.length();
    cout << "Count of operations to make a binary string \"ab\" free are: " 
         << operations_ab_free(str, length) << endl;
    return 0;
}

আউটপুট

Count of operations to make a binary string "ab" free are: 4