จำนวนสูงสุดของการลบลำดับย่อยที่กำหนดจากสตริงใน C++

ภารกิจคือการค้นหาจำนวนสูงสุดของการลบลำดับย่อยที่กำหนดออกจากสตริง ให้ Astring และเราต้องหาจำนวนสูงสุดของ subsequence 'abc' ที่สามารถตัดออกจาก string ได้

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง:

อินพุต

s = ‘dnabcxy’

ผลลัพธ์

1

คำอธิบาย − สามารถพบลำดับย่อยของ 'abc' ได้เพียงรายการเดียวในสตริงที่กำหนด ('dnabcxy') ดังนั้นเอาต์พุตจึงเป็น 1

อินพุต

s = ‘zcabcxabc’

ผลลัพธ์

2 (‘zcabcxabc’)

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• ในฟังก์ชัน Max() เริ่มต้นตัวแปร i, a, ab, abc ด้วยค่า =0 และประเภท int

• วนรอบจาก i=0 จนถึง I

• ภายในลูปตรวจสอบว่า (s[i] =='a') ถ้าใช่ ให้เพิ่มค่า a.

• อย่างอื่น ตรวจสอบว่า (s[i] =='b') ถ้าเป็นจริง ให้ตรวจสอบอีกครั้งว่า (a> 0) หากเงื่อนไขทั้งสองเป็นจริง ให้ลดค่า a ขึ้น 1 และเพิ่มค่า ab

• สุดท้าย ตรวจสอบว่า (s[i] =='c') ถ้าเป็นจริง ให้ตรวจสอบอีกครั้งว่า (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