สมมติว่าเรามีสตริง S. S มีอักขระสองประเภทใน S, 'x' และ 'a' เราต้องนับว่าอะไรจะเป็นสตริงที่ยาวที่สุดหลังจากลบอักขระบางตัวใน S เพื่อให้กลายเป็นสตริงที่ดี สตริงจะดีหากมีความยาวเกินครึ่งซึ่งเต็มไปด้วยอักขระ 'a'
ดังนั้น หากอินพุตเป็นเหมือน S ="xaxxxa" ผลลัพธ์จะเป็น 3 เพราะหากเราลบ 4 'x's ออก สตริงจะเป็น "xaa" และนี่คือสตริงที่ดีที่มีความยาว 3
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
x := 2 * count the number of 'a' in S n := size of S return minimum of n and x
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
"xaxxxxa"
ผลลัพธ์
3
