แยกสตริงในสตริงที่สมดุลใน C ++

ดังที่เราทราบดีว่าสตริงที่สมดุลคือสตริงที่มีอักขระด้านซ้ายและขวาเท่ากัน สมมติว่าเรามีสตริงที่สมดุลแล้วแยกเป็นจำนวนสูงสุดของสตริงที่สมดุล เราต้องส่งคืนจำนวนสูงสุดของสตริงที่สมดุลที่แยกออกมา ดังนั้นหากสตริงคือ "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 และทำลายลูป
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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