C++での文字列からの特定のサブシーケンスの削除の最大数

与えられたタスクは、文字列から与えられたサブシーケンスの削除の最大数を見つけることです。文字列sが指定されているため、文字列から削除できるサブシーケンス「abc」の最大数を見つける必要があります。

例を使用して、私たちがしなければならないことを理解しましょう：

入力

s = ‘dnabcxy’

出力

1

説明 −指定された文字列（「dnabcxy」）には「abc」のサブシーケンスが1つしか見つからないため、出力は1になります。

入力

s = ‘zcabcxabc’

出力

2 (‘zcabcxabc’)

以下のプログラムで使用されるアプローチは次のとおりです

• Max（）関数で、変数i、a、ab、abcを値=0でint型で初期化します。

• i =0からIまでループします

• ループ内で（s [i] ==‘a’）かどうかを確認し、そうである場合は、aの値をインクリメントします。

• それ以外の場合は、（s [i] ==‘b’）かどうかを確認し、trueの場合は、（a> 0）かどうかをもう一度確認します。両方の条件が当てはまる場合は、aの値を1減らし、abの値を増やします。

• 最後に、（s [i] ==‘c’）かどうかを確認し、trueの場合は、（ab> 0）かどうかをもう一度確認します。両方の条件が当てはまる場合は、abの値を1減らし、abcの値を増やします。

• abcを返す

例

#include <bits/stdc++.h>
using namespace std;
int Max(string s){
   int i=0, a=0, ab=0, abc=0;
   for (i = 0; i < s.length(); i++){
      if (s[i] == 'a'){
         a++;
      }
      else if (s[i] == 'b'){
         if (a > 0){
            a--;
            ab++;
         }
      }
      else if (s[i] == 'c'){
         if (ab > 0){
            ab--;
            abc++;
         }
      }
   }
   return abc;
}
//main function
int main(){
   string s = "zcabcxabc";
   cout << Max(s);
   return 0;
}

出力

2