สมมติว่าเรามีสตริง S S มีตัวอักษร 2 ชนิดคือ 'x' และ 'a' เราต้องนับว่าสตริงที่ยาวที่สุดที่เหลือหลังจากลบตัวอักษรบางส่วนใน S จะยาวเท่าไร จนกว่าจะกลายเป็น "สตริงดี" สตริงดีคือ สตริงที่มีตัวอักษร 'a' มากกว่าครึ่งหนึ่งของความยาวอย่างเคร่งครัด
เช่น ถ้าค่าที่ป้อนเข้าเป็น S = "xaxxxxa" ผลลัพธ์จะได้ 3 เพราะถ้าลบ 'x' 4 ตัว สตริงจะกลายเป็น "xaa" ซึ่งเป็นสตริงดีที่มีความยาว 3
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
x := 2 * นับจำนวน 'a' ใน S n := ขนาดของ S คืนค่า min(n, 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
