Giả sử chúng ta có một chuỗi S. S chứa hai loại ký tự trong S, là 'x' và 'a'. Chúng ta phải đếm chuỗi dài nhất còn lại sau khi xóa một vài ký tự trong S để nó trở thành chuỗi tốt. Một chuỗi là tốt nếu nó có hơn một nửa độ dài được lấp đầy bằng ký tự 'a'.
Ví dụ, nếu đầu vào là S = "xaxxxxa", thì đầu ra sẽ là 3, vì nếu xóa 4 'x', chuỗi sẽ là "xaa" và đây là chuỗi tốt có độ dài 3.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
x := 2 * đếm số 'a' trong S n := kích thước của S return minimum của n và x
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(string S) { int x = 2 * count(S.begin(), S.end(), 'a') - 1; int n = S.size(); return min(n, x); } int main() { string S = "xaxxxxa"; cout << solve(S) << endl; }Đầu vào
"xaxxxxa"
Đầu ra
3