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

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

ตัวอย่าง

อินพุต

s = 'dnabcxy'

เอาต์พุต

คำอธิบาย

พบ subsequence 'abc' เพียง 1 ครั้งในสตริงที่กำหนด ('dnabcxy') ดังนั้นผลลัพธ์คือ 1

อินพุต

s = 'zcabcxabc'

เอาต์พุต

2 ('zcabcxabc')

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

ใน Max() เริ่มต้นตัวแปร i, a, ab, abc = 0 ทั้งหมดเป็น int
ลูป i = 0 ถึง i < s.length()
ในลูป ถ้า s[i] == 'a' เพิ่ม a
มิฉะนั้น ถ้า s[i] == 'b' ตรวจสอบ if (a > 0) ถ้าทั้งคู่จริง ลด a ลง 1 เพิ่ม ab
สุดท้าย ถ้า s[i] == 'c' ตรวจสอบ if (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;
}

int main() {
    string s = "zcabcxabc";
    cout << Max(s);
    return 0;
}