समस्या विवरण
केवल A और B से बनी एक स्ट्रिंग दी गई है। हम दिए गए स्ट्रिंग को किसी भी वर्ण को टॉगल करके दूसरी स्ट्रिंग में बदल सकते हैं। इस प्रकार दिए गए स्ट्रिंग के कई परिवर्तन संभव हैं। कार्य अधिकतम वजन परिवर्तन का वजन ढूंढना है।
स्ट्रिंग का वजन नीचे दिए गए सूत्र का उपयोग करके गणना की जाती है −
स्ट्रिंग का वजन = कुल जोड़ियों का वजन + एकल वर्णों का वजन - कुल टॉगल की संख्या।
लगातार दो वर्णों को एक जोड़ी माना जाता है केवल यदि वे अलग हैं।
एकल जोड़ी का वजन (दोनों वर्ण अलग हैं) = 4
एकल वर्ण का वजन = 1
यदि इनपुट स्ट्रिंग है − "AA" तो आउटपुट 3 होगा −
दिए गए स्ट्रिंग के परिवर्तन हैं "AA", "AB", "BA" और "BB"।
अधिकतम वजन परिवर्तन "AB" या "BA" है। और वजन है "एक जोड़ी - एक टॉगल" = 4-1 = 3।
एल्गोरिदम
1. यदि (n == 1) maxWeight(str[0..n-1]) = 1 2. अन्यथा यदि str[0] != str[1] maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1]) 3. अन्यथा maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1])
उदाहरण
#include<bits/stdc++.h> using namespace std; int getMaxRec(string &str, int i, int n, int lookup[]){ if (i >= n) { return 0; } if (lookup[i] != -1) { return lookup[i]; } int ans = 1 + getMaxRec(str, i + 1, n, lookup); if (i + 1 < n) { if (str[i] != str[i+1]) { ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans); } else { ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans); } } return lookup[i] = ans; } int getMaxWeight(string str){ int n = str.length(); int lookup[n]; memset(lookup, -1, sizeof lookup); return getMaxRec(str, 0, str.length(), lookup); } int main(){ string str = "AA"; cout << "Result = " << getMaxWeight(str) << endl; return 0; }आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है −
Result = 3
