Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Số lần loại bỏ tối đa chuỗi con cho trước từ xâu trong C++

Nhiệm vụ: tìm số lần loại bỏ tối đa chuỗi con 'abc' từ xâu cho trước.

Ví dụ 1

Đầu vào** –

s = 'dnabcxy'

Đầu ra** – 1

Giải thích** – Chỉ tìm thấy 1 chuỗi con 'abc'.

Ví dụ 2

Đầu vào** –

s = 'zcabcxabc'

Đầu ra** – 2

Phương pháp (Đếm kiểu stack)

  • Duyệt xâu, duy trì bộ đếm: a (số 'a' chưa ghép), ab (số cặp 'ab' chưa ghép), abc (số 'abc' hoàn thành).
  • Gặp 'a': a++.
  • Gặp 'b': nếu a>0 thì a--, ab++.
  • Gặp 'c': nếu ab>0 thì ab--, abc++.
  • Kết quả = abc.

Cách này tìm số chuỗi con 'abc' không chồng lấn theo thứ tự xuất hiện.

Ví dụ

#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;
}

Đầu ra

2