C++-এ 'a' সংখ্যা 'b'-র চেয়ে বেশি হয় এমন প্রিফিক্সের সংখ্যা (Prefixes with More a than b)

এই সমস্যাতে, 'a' এবং 'b' দিয়ে গঠিত একটি স্ট্রিং str এবং একটি পূর্ণসংখ্যা N দেওয়া থাকে। str কে N বার যোগ করে একটি বড় স্ট্রিং তৈরি করুন। এই বড় স্ট্রিংয়ে কতগুলো সাবস্ট্রিং আছে যেখানে 'a'-র সংখ্যা 'b'-র চেয়ে বেশি, তা বের করতে হবে।

উদাহরণ

ইনপুট: aab 2 → আউটপুট: ৯

তैयার স্ট্রিং: aabaab

মান্য সাবস্ট্রিং: 'a', 'aa', 'aab', 'aaba', 'aabaa', 'aabaab', 'aba', 'baa', 'abaa'

অপ্টিমাইজড পদ্ধতি

পুরো স্ট্রিং না বানিয়ে মূল str-র প্রিফিক্স অ্যানালাইসিস করে সমাধান করা যায়। কাউন্ট a এবং b ট্র্যাক করুন এবং N-বার পুনরাবৃত্তির প্রভাব গণনা করুন।

C++ প্রোগ্রাম উদাহরণ

#include <iostream>
#include <string.h>
using namespace std;

int prefixCount(string str, int n) {
    int a = 0, b = 0, count = 0;
    int len = str.size();
    
    // প্রথম পাস
    for (int i = 0; i < len; i++) {
        if (str[i] == 'a') a++;
        if (str[i] == 'b') b++;
        if (a > b) count++;
    }
    
    if (count == 0 || n == 1) return count;
    if (count == len || a - b == 0) return count * n;
    
    int n2 = n - 1, count2 = 0;
    while (n2 != 0) {
        for (int i = 0; i < len; i++) {
            if (str[i] == 'a') a++;
            if (str[i] == 'b') b++;
            if (a > b) count2++;
        }
        count += count2;
        n2--;
        if (count2 == 0) break;
        if (count2 == len) {
            count += n2 * count2;
            break;
        }
        count2 = 0;
    }
    return count;
}

int main() {
    string str = "aba";
    int N = 2;
    cout << "The string created by using '" << str << "' " << N 
         << " times has " << prefixCount(str, N) 
         << " substring with count of a greater than count of b";
    return 0;
}

আউটপুট

The string created by using 'aba' 2 times has 5 substring with count of a greater than count of b