ধরুন আমাদের এন দৈর্ঘ্যের একটি স্ট্রিং S আছে, যেখানে কেবল দুটি ধরণের অক্ষর রয়েছে, 'A' বা 'P'। একটি সারিতে n ছাত্র আছে, যদি S[i] ='A' হয় তাহলে ith ছাত্র রাগান্বিত হয়, যদি এটি 'P' হয় তাহলে বলে S[i] ধৈর্যশীল। সূচীতে একজন রাগান্বিত ছাত্র প্রতি মিনিটে সূচক i+1-এ রোগীর ছাত্রকে আঘাত করবে, এবং শেষ ছাত্রের জন্যও সে রাগান্বিত, সে কাউকে আঘাত করতে পারবে না। রোগীর ছাত্রকে আঘাত করার পর সেই ছাত্রও রেগে যায়। আমাদের ন্যূনতম মিনিট খুঁজে বের করতে হবে তার পরে কোন নতুন ছাত্র রাগ করবে না।
সুতরাং, যদি ইনপুটটি S ="PPAPP" এর মত হয়, তাহলে আউটপুট হবে 2, কারণ প্রথম মিনিটের পরে, স্ট্রিংটি হবে "PPAAP", তারপর দ্বিতীয় মিনিটে "PPAAA", তাহলে নতুন কোনো শিক্ষার্থী আবার রাগ করবে না।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
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
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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
