C++의 문자열에서 주어진 하위 시퀀스의 최대 제거 수

<시간/>

주어진 작업은 문자열에서 주어진 하위 시퀀스의 최대 제거 수를 찾는 것입니다. Astring s가 주어지고 문자열에서 제거할 수 있는 하위 시퀀스 'abc'의 최대 수를 찾아야 합니다.

이제 예제를 사용하여 수행해야 하는 작업을 이해해 보겠습니다.

입력

s = ‘dnabcxy’

출력

설명 − 주어진 문자열('dnabcxy')에서 'abc'의 하위 시퀀스 하나만 찾을 수 있으므로 출력은 1입니다.

입력

s = ‘zcabcxabc’

출력

2 (‘zcabcxabc’)

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

Max() 함수에서 값이 0이고 int 유형인 변수 i, a, ab, abc를 초기화합니다.
i=0에서 I 까지 루프
루프 내에서 if (s[i] =='a'), 그렇다면 a의 값을 증가시킵니다.
그렇지 않으면 (s[i] =='b')인지 확인하고, true이면 (a> 0)인지 다시 확인합니다. 두 조건이 모두 참이면 의 값을 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;
}