C++でバランスの取れた文字列に文字列を分割する

バランスの取れた文字列は、左右の文字の数が等しい文字列であることがわかっています。バランスの取れた文字列が最大量のバランスの取れた文字列に分割されているとします。分割されたバランスの取れた文字列の最大量を返す必要があります。したがって、文字列が「RLRRLLRLRL」の場合、4つのバランスの取れた文字列があるため、出力は4になります。 「RL」、「RRLL」、「RL」、および「RL」の各サブストリングには、同じ量のLとRがあります。

これを解決するには、次の手順に従います-

• cnt：=0、ans：=0を初期化します
• for i：=0から文字列のサイズ
  • cnt：=0
  • for j：=i to size of 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"

出力

3