স্ট্রিং-এ ব্যালেন্সিং পজিশনের সংখ্যা খুঁজে বের করা (C++)

ধরি একটি স্ট্রিং দেওয়া আছে। সেটি থেকে ব্যালেন্সিং পজিশনের সংখ্যা বের করতে হবে যেখানে বাম এবং ডান অংশে একই ক্যারেক্টার থাকে (ফ্রিকোয়েন্সি विचaronne না)। উদাহরণস্বরূপ, স্ট্রিং "ABAABA" হলে ব্যালেন্সিং পজিশন ৩টি: AB|AABA, ABA|ABA, ABAA|BA।

অ্যালগরিদম

1. প্রথমে স্ট্রিং ট্র্যাভার্স করে right[] অ্যারেতে সব ক্যারেক্টারের কাউন্ট রাখা হয়।
2. তারপর বাম থেকে ডান দিকে ট্র্যাভার্স করা হয়। প্রতিটি ক্যারেক্টারের জন্য left[]-এ কাউন্ট বাড়ানো এবং right[]-এ কমানো হয়।
3. যেকোনো পয়েন্টে, যদি left[]-এ নন-জিরো মান 가진 সব ক্যারেক্টারের right[]-এও নন-জিরো মান থাকে এবং বিপরীতটিও সত্য হয়, তবে সেটি একটি ব্যালেন্সিং পজিশন এবং রেজাল্ট বাড়ানো হয়।

উদাহরণ

#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;

int countBalancePoints(string str) {
    int left[MAX_CHAR] = {0};
    int right[MAX_CHAR] = {0};
    for (int i = 0; i < str.length(); i++)
        right[str[i]]++;

    int count = 0;
    for (int i = 0; i < str.length(); i++) {
        left[str[i]]++;
        right[str[i]]--;
        int j;
        for (j = 0; j < MAX_CHAR; j++) {
            if ((left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
                break;
        }
        if (j == MAX_CHAR)
            count++;
    }
    return count;
}

int main() {
    char str[] = "ABAABA";
    cout << "Number of balance points: " << countBalancePoints(str);
    return 0;
}

আউটপুট

Number of balance points: 3