আমরা জানি যে ভারসাম্যপূর্ণ স্ট্রিংগুলি হল সেইগুলি যেগুলিতে বাম এবং ডান অক্ষরের সমান পরিমাণ রয়েছে। ধরুন আমাদের একটি ভারসাম্যপূর্ণ স্ট্রিং আছে এটিকে সর্বোচ্চ পরিমাণে সুষম স্ট্রিংয়ে বিভক্ত করেছি। আমাদের বিভক্ত ব্যালেন্সড স্ট্রিংগুলির সর্বাধিক পরিমাণ ফেরত দিতে হবে। সুতরাং যদি স্ট্রিংটি "RLRRLLRLRL" হয়, তাহলে আউটপুট হবে 4. কারণ চারটি সুষম স্ট্রিং আছে। “RL”, “RRLL”, “RL” এবং “RL” প্রতিটি সাবস্ট্রিংয়ে সমান পরিমাণ L এবং R আছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- cnt :=0, এবং উত্তর :=0 শুরু করুন
- এর জন্য i :=0 থেকে স্ট্রিং এর আকার
- cnt :=0
- j এর জন্য :=i থেকে স্ট্রিং এর সাইজ −
- যদি s[j] ='R', তাহলে cnt 1 দ্বারা বাড়ান অন্যথা cnt 1 দ্বারা কমান
- যদি j – i> 0 এবং cnt =0 হয়, তাহলে উত্তর 1, i :=j দ্বারা বাড়ান এবং লুপ ভেঙে দিন
- উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedStringSplit(string s) {
int cnt = 0;
int ans = 0;
for(int i =0;i<s.size();i++){
cnt = 0;
for(int j = i;j<s.size();j++){
if(s[j] == 'R')cnt++;
else cnt--;
if(j-i>0 && cnt == 0 ){
ans++;
i=j;
break;
}
//cout << i << " " << j <<" "<< cnt << endl;
}
}
return ans;
}
};
main(){
Solution ob;
cout << ob.balancedStringSplit("RLLLLRRRLR");
} ইনপুট
"RLLLLRRRLR"
আউটপুট
3
