मान लीजिए हमारे पास लंबाई n की एक स्ट्रिंग S है, जिसमें केवल दो प्रकार के वर्ण हैं, 'A' या 'P'। एक पंक्ति में n छात्र हैं, i-वां छात्र नाराज है यदि S[i] = 'A', यदि यह 'P' है तो यह कहता है कि S[i] धैर्यवान है। इंडेक्स 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
