C++ प्रोग्राम न्यूनतम गिनने के लिए कि कितने मिनट बाद कोई नया नाराज़ छात्र नहीं होगा

मान लीजिए कि हमारे पास लंबाई n की एक स्ट्रिंग S है, जिसमें केवल दो प्रकार के वर्ण हैं, 'A' या 'P'। एक पंक्ति में n छात्र हैं, यदि S[i] ='A' है, तो ith छात्र क्रोधित है, यदि यह 'P' है तो यह कहता है कि S[i] धैर्यवान है। इंडेक्स पर गुस्सा छात्र मैं हर मिनट में इंडेक्स i+1 में रोगी छात्र को मारूंगा, और आखिरी छात्र के लिए भी वह गुस्से में है, वह किसी को नहीं मार सकता। एक मरीज छात्र को पीटने के बाद वह छात्र भी नाराज हो जाता है. हमें कम से कम मिनटों का पता लगाना होगा ताकि उसके बाद कोई नया छात्र नाराज न हो।

तो, अगर इनपुट एस ="पीपीएपीपी" की तरह है, तो आउटपुट 2 होगा, क्योंकि पहले मिनट के बाद, स्ट्रिंग "पीपीएएपी" होगी, फिर दूसरे मिनट में "पीपीएएए" होगी, तो कोई नया छात्र फिर से नाराज नहीं होता है।

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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