สมมติว่าเรามีสตริง S ความยาว n มีตัวอักษรเพียง 2 ชนิดคือ 'A' หรือ 'P' มีนักเรียนนักเรียนนั่งเรียง n คน นักเรียนคนที่ i โกรธถ้า S[i] = 'A' ถ้าเป็น 'P' หมายถึง S[i] เป็นคนอดทน นักเรียนโกรธที่ดัชนี i จะตบนักเรียนอดทนที่ดัชนี i+1 ทุกนาที และสำหรับนักเรียนคนสุดท้ายแม้จะโกรธก็ไม่สามารถตบใครได้ หลังจากตบนักเรียนอดทน คนนั้นก็จะกลายเป็นโกรธ เราต้องหานาทีขั้นต่ำหลังจากนั้นที่ไม่มีนักเรียนใหม่โกรธอีก
เช่น ถ้าค่าที่ป้อนเข้าเป็น S = "PPAPP" ผลลัพธ์จะได้ 2 เพราะหลังนาทีแรก สตริงจะเป็น "PPAAP" แล้วนาทีที่สอง "PPAAA" แล้วไม่มีนักเรียนใหม่โกรธอีก
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ S ans := 0, cnt = 0 สำหรับ i := n - 1 เมื่อ i >= 0 ลด i ทีละ 1 ทำ: ถ้า S[i] เท่ากับ 'P' แล้ว: (เพิ่ม cnt ขึ้น 1) มิฉะนั้น ans := max(ans, cnt) cnt := 0 คืนค่า ans
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; int solve(string S) { int n = S.size(); int ans = 0, cnt = 0; for (int i = n - 1; i >= 0; i--) { if (S[i] == 'P') { cnt++; } else { ans = max(ans, cnt); cnt = 0; } } return ans; } int main() { string S = "PPAPP"; cout << solve(S) << endl; }
ข้อมูลนำเข้า
PPAPP
ข้อมูลส่งออก
2
