ধরুন আমাদের একটি স্ট্রিং আছে। আমাদের সেই স্ট্রিংটিতে ব্যালেন্সিং পজিশন কাউন্ট খুঁজে বের করতে হবে যেখান থেকে স্ট্রিংয়ের বাম এবং ডান অংশে একই অক্ষর রয়েছে। অক্ষর ফ্রিকোয়েন্সি কোন ব্যাপার না. তাই যদি স্ট্রিংটি "ABAABA" হয়, তাহলে ব্যালেন্সিং পজিশনের সংখ্যা হল 3। এই পজিশনগুলি হল AB|AABA, ABA|ABA, ABAA|BA৷
এটি সমাধানের জন্য, আমরা কিছু কার্যকর পদ্ধতি অনুসরণ করব। স্ট্রিংটি অতিক্রম করার পরে আমরা প্রথমে সমস্ত অক্ষরের গণনা সহ সঠিক [] অনুভব করি। তারপর বাম থেকে ডানে স্ট্রিংটি অতিক্রম করুন। প্রতিটি অক্ষরের জন্য আমরা বাম দিকে তার সংখ্যা বৃদ্ধি করি [] এবং ডানে গণনা হ্রাস করি। যেকোন বিন্দু অতিক্রম করার জন্য, যদি বামে অ-শূন্য মান আছে এমন সমস্ত অক্ষরগুলির ডানদিকেও অ-শূন্য মান থাকে এবং এর বিপরীতেও সত্য হয়। তারপর ফলাফল বৃদ্ধি করুন।
উদাহরণ
#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);
} আউটপুট
Number of balance points: 3
