C++에서 균형 문자열의 문자열 분할

<시간/>

균형 잡힌 문자열은 동일한 양의 왼쪽 및 오른쪽 문자가 있는 문자열이라는 것을 알고 있습니다. 균형 잡힌 문자열이 최대 균형 문자열로 분할된다고 가정합니다. 분할된 균형 문자열의 최대량을 반환해야 합니다. 따라서 스트링이 "RLRRLLRLRL"이면 4개의 균형 스트링이 있으므로 출력은 4가 됩니다. "RL", "RRLL", "RL" 및 "RL" 각 부분 문자열에는 동일한 양의 L 및 R이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

초기화 cnt :=0 및 ans :=0
for i :=0에서 문자열 크기까지
- cnt :=0
- for j :=i to string −
  - 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"