जैसा कि हम जानते हैं कि संतुलित स्ट्रिंग्स वे हैं जिनमें बाएं और दाएं कैरेक्टर्स की समान मात्रा होती है। मान लें हमारे पास एक संतुलित स्ट्रिंग s है जिसे इसे अधिकतम मात्रा में संतुलित स्ट्रिंग्स में विभाजित करना है। हमें विभाजित संतुलित स्ट्रिंग्स की अधिकतम मात्रा लौटानी है। तो यदि स्ट्रिंग “RLRRLLRLRL” है, तो आउटपुट 4 होगा। क्योंकि चार संतुलित स्ट्रिंग्स हैं। “RL”, “RRLL”, “RL” और “RL” प्रत्येक सबस्ट्रिंग में L और R की समान मात्रा है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- cnt := 0, और ans := 0 इनिशियलाइज़ करें
- i := 0 से स्ट्रिंग के आकार तक
- cnt := 0
- j := i से स्ट्रिंग के आकार तक घटाएं
- यदि s[j] = ‘R’, तो cnt को 1 से बढ़ाएं अन्यथा cnt को 1 से घटाएं
- यदि j – i > 0 और cnt = 0, तो ans को 1 से बढ़ाएं, i := j, और लूप तोड़ें
- 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
