सी ++ में संतुलित स्ट्रिंग्स में एक स्ट्रिंग को विभाजित करें

जैसा कि हम जानते हैं कि संतुलित तार वे होते हैं जिनमें बाएँ और दाएँ वर्णों की समान मात्रा होती है। मान लीजिए कि हमारे पास एक संतुलित स्ट्रिंग है जो इसे संतुलित स्ट्रिंग्स की अधिकतम मात्रा में विभाजित करती है। हमें विभाजित संतुलित तारों की अधिकतम मात्रा वापस करनी होगी। तो यदि स्ट्रिंग "RLRRLLRLRL" है, तो आउटपुट 4 होगा। क्योंकि चार संतुलित स्ट्रिंग हैं। "आरएल", "आरआरएलएल", "आरएल" और "आरएल" प्रत्येक सबस्ट्रिंग में एल और आर की बराबर मात्रा होती है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सीएनटी प्रारंभ करें:=0, और उत्तर:=0
• i :=0 से स्ट्रिंग के आकार के लिए
  • सीएनटी:=0
  • j :=i से स्ट्रिंग के आकार के लिए -
    • यदि s[j] ='R' है, तो cnt को 1 से बढ़ाएं अन्यथा cnt को 1 से घटाएं
    • अगर j – i> 0 और cnt =0, तो ans को 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