मान लीजिए हमारे पास n वर्णों का एक स्ट्रिंग S है। वर्ण या तो '+' या '-' होंगे। पत्थरों का एक ढेर है, n बार हमने या तो ढेर से एक पत्थर लिया या ढेर में एक पत्थर जोड़ा। ढेर प्रत्येक पत्थर लेने के ऑपरेशन से पहले गैर-खाली था। हमें उन पत्थरों की न्यूनतम संभव संख्या ढूंढनी है जो इन ऑपरेशनों को करने के बाद ढेर में हो सकते हैं। यदि हमने iवें ऑपरेशन पर पत्थर लिया, तो S[i] "-" के बराबर है, यदि जोड़ा, तो S[i] "+" के बराबर है।
उदाहरण के लिए, यदि इनपुट S = "++-++" है, तो आउटपुट 3 होगा। यदि शुरुआत में ढेर में 0 पत्थर थे, तो ऑपरेशन करने के बाद पत्थरों की संख्या 3 के बराबर होगी।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of S for initialize i := 0, when i < n, update (increase i by 1), do: res := (if S[i] is same as '-', then maximum of res - 1 and 0, otherwise res + 1) return res
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(string S){ int n = S.size(), res = 0; for (int i = 0; i < n; i++) res = (S[i] == '-') ? max(res - 1, 0) : res + 1; return res; } int main(){ string S = "++-++"; cout << solve(S) << endl; }
इनपुट
"++-++"
आउटपुट
3