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