যেমন আমরা জানি ব্যালেন্সড স্ট্রিংস হলো যেগুলোর লেফট এবং রাইট ক্যারেক্টারের কয়ান্টিটি সমান। ধরুন আমাদের একটি ব্যালেন্সড স্ট্রিং s আছে এটি সর্বোচ্চ পরিমাণে ব্যালেন্সড স্ট্রিংসে ভাগ করুন। আমাদের সর্বোচ্চ কতগুলো ব্যালেন্সড স্ট্রিংতে ভাগ করা যায় সেটি রিটার্ন করতে হবে। তাই যদি স্ট্রিংটি “RLRRLLRLRL” হয়, তবে আউটপুট হবে ৪। কারণ চারটি ব্যালেন্সড স্ট্রিং আছে। “RL”, “RRLL”, “RL” এবং “RL” প্রতিটি সাবস্ট্রিং-এ L এবং R সমান পরিমাণে আছে।
এটি সমাধানের জন্য, আমরা নিচের ধাপগুলো অনুসরণ করব −
- initialize cnt := 0, and ans := 0
- for i := 0 to size of the string
- cnt := 0
- for j := i to size of string −
- if s[j] = ‘R’, then increase cnt by 1 otherwise decrease cnt by 1
- if j – i > 0 and cnt = 0, then increase ans by 1, i := j, and break the loop
- return ans
উদাহরণ
বুঝতে নিচের ইমপ্লিমেন্টেশনটি দেখুন −
#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
