Giả sử chúng ta có một chuỗi S. S chứa hai loại ký tự trong S, 'x' và 'a'. Chúng ta phải đếm xem đâu sẽ là chuỗi dài nhất còn lại sau khi loại bỏ một vài ký tự trong S để nó trở thành chuỗi tốt. Một chuỗi sẽ tốt nếu nó có nhiều hơn một nửa chiều dài chứa ký tự 'a'.
Vì vậy, nếu đầu vào là S ="xaxxxxa", thì đầu ra sẽ là 3, bởi vì nếu chúng ta loại bỏ 4 'x, chuỗi sẽ là "xaa" và đây là một chuỗi tốt có độ dài là 3.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
x := 2 * count the number of 'a' in S n := size of S return minimum of n and x
Ví dụ
Hãy cùng chúng tôi xem cách 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