Giả sử chúng ta có một chuỗi S có độ dài n, chỉ có hai loại ký tự là 'A' hoặc 'P'. Có n học sinh liên tiếp, học sinh thứ i tức giận nếu S [i] ='A', nếu là 'P' thì S [i] là người kiên nhẫn. Một học sinh tức giận ở chỉ số i sẽ đánh học sinh kiên nhẫn ở chỉ số i + 1 trong mỗi phút, và đối với học sinh cuối cùng dù tức giận, anh ta cũng không thể đánh ai. Sau khi đánh một học sinh kiên nhẫn, học sinh đó cũng tức giận. Chúng tôi phải tìm những phút tối thiểu để sau đó không có học sinh mới nào nổi giận.
Vì vậy, nếu đầu vào là S ="PPAPP", thì đầu ra sẽ là 2, vì sau phút đầu tiên, chuỗi sẽ là "PPAAP", sau đó đến phút thứ hai là "PPAAA", sau đó không có học viên mới nào nổi giận nữa.
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 -
n := size of S ans := 0, cnt = 0 for initialize i := n - 1, when i >= 0, update (decrease i by 1), do: if S[i] is same as 'P', then: (increase cnt by 1) Otherwise ans := maximum of ans and cnt cnt := 0 return ans
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 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;
} Đầu vào
PPAPP
Đầu ra
2