समस्या कथन
केवल ए और बी से मिलकर एक स्ट्रिंग को देखते हुए। हम किसी भी कैरेक्टर को टॉगल करके दिए गए स्ट्रिंग को दूसरी स्ट्रिंग में बदल सकते हैं। इस प्रकार दिए गए स्ट्रिंग के कई परिवर्तन संभव हैं। कार्य अधिकतम वजन परिवर्तन के वजन का पता लगाना है।
एक डंक के वजन की गणना निम्न सूत्र का उपयोग करके की जाती है -
Weight of string = Weight of total pairs + weight of single characters - Total number of toggles.
-
दो क्रमागत वर्णों को एक जोड़ा तभी माना जाता है जब वे भिन्न हों।
-
एक जोड़ी का भार (दोनों वर्ण भिन्न हैं) =4
-
एक वर्ण का भार =1
यदि इनपुट स्ट्रिंग है - "AA" तो आउटपुट 3 होगा -
-
दिए गए स्ट्रिंग के रूपांतरण "AA", "AB", "BA" और "BB" हैं।
-
अधिकतम वजन परिवर्तन "एबी" या "बीए" है। और वजन "एक जोड़ी - एक टॉगल" =4-1 =3 है।
एल्गोरिदम
1. If (n == 1) maxWeight(str[0..n-1]) = 1 2. Else If str[0] != str[1] maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1]) 3. Elses 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