Tách một chuỗi trong chuỗi cân bằng trong C ++

Như chúng ta biết rằng các chuỗi cân bằng là những chuỗi có số lượng ký tự trái và phải bằng nhau. Giả sử chúng ta có một chuỗi cân bằng s chia nó ra với số lượng lớn nhất của chuỗi cân bằng. Chúng ta phải trả lại số lượng chuỗi cân bằng đã tách tối đa. Vì vậy, nếu chuỗi là "RLRRLLRLRL", thì đầu ra sẽ là 4. vì có bốn chuỗi cân bằng. “RL”, “RRLL”, “RL” và “RL” mỗi chuỗi con có số lượng L và R. bằng nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• khởi tạo cnt:=0 và ans:=0
• for i:=0 to size of string
  • cnt:=0
  • for j:=i to size of string -
    • nếu s [j] =‘R’, thì tăng cnt lên 1 nếu không thì giảm cnt đi 1
    • nếu j - i> 0 và cnt =0, sau đó tăng ans lên 1, i:=j và ngắt vòng lặp
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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");
}

Đầu vào

"RLLLLRRRLR"

Đầu ra

3