हमें केवल (,),{,},[,] वर्णों वाली एक स्ट्रिंग दी गई है। लक्ष्य ऐसी स्ट्रिंग की अधिकतम लंबाई ज्ञात करना है ताकि आसन्न वर्णों की अदला-बदली करके या किसी वर्ण को हटाकर यह संतुलित हो जाए। हम आसन्न वर्णों की तुलना करके ऐसा करेंगे, यदि वे एक दूसरे के विपरीत हैं तो उन्हें बदला जा सकता है। ( }{,)(,][ अदला-बदली की जा सकती है, जबकि {{,)),[[,}},)),]] की अदला-बदली नहीं की जा सकती )।
साथ ही अगर किसी कैरेक्टर में मैचिंग पेयर नहीं है तो उसे हटाया भी जा सकता है। ("{{}][“, यहां पहले { हटाया जा सकता है और संतुलित स्ट्रिंग लंबाई 4 हो जाती है)
इनपुट
str[]= “ {{{}}{]]][()” length 12 आउटपुट
Maximum length of balances string: 8
स्पष्टीकरण − str[0] और str[1] की अदला-बदली नहीं की जा सकती, str[0]=“{{}}{]]][()” को हटा दें मूल str[1] और str[2] की अदला-बदली नहीं की जा सकती, str को हटा दें[ 1]="{}}{]]][()" {} संतुलित हैं }{ अदला-बदली की जा सकती है, अगले 2 को हटा दें]], स्वैप करें [और () भी संतुलित हैं अंतिम स्ट्रिंग है {}{}[]( ) लंबाई 8 है।
इनपुट
str[]= “(((((()” length 7.)
आउटपुट
str[]= “(((((()” length 7.)
स्पष्टीकरण -केवल str[5] और str[6] संतुलित हैं, सभी को हटा दें। अंतिम स्ट्रिंग ()। लंबाई 2 है
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
कैरेक्टर ऐरे str[] मूल स्ट्रिंग को स्टोर करता है। पूर्णांक लंबाई स्ट्रिंग की लंबाई संग्रहीत करती है।
-
फ़ंक्शन maxBalancedStr (char str[], int len) स्ट्रिंग और उसकी लंबाई के एस्पेरामीटर लेता है और संतुलित स्ट्रिंग की अधिकतम लंबाई लौटाता है।
-
ऐसी स्ट्रिंग की लंबाई को स्टोर करने के लिए वैरिएबल काउंट का इस्तेमाल शुरू में 0.
. किया जाता है -
पहले वर्ण से स्ट्रिंग को ट्रैवर्स करना शुरू करें और जांचें कि क्या आसन्न चरित्र को दोनों को संतुलित करने के लिए बदला जा सकता है। या अगर वे पहले से ही संतुलित हैं, तो गिनती में 2 की वृद्धि करें।
-
जोड़े के लिए ऐसा करें, (),)(और {},}{ और [],][, अगर ऐसे जोड़े मौजूद हैं तो वेतन वृद्धि भी अगले वर्ण पर जाने के लिए करें।
-
अंत में गिनती संतुलित स्ट्रिंग की लंबाई संग्रहीत करती है।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of
// the longest balanced sub-string
int maxBalancedStr(char str[20], int len){
int count=0;
// Traversing the string
for (int i = 0; i <len;i++) {
// Check type of parentheses and
// incrementing count for it
if((str[i]=='(' && str[i+1]==')') || (str[i]==')' && str[i+1]=='(')) //can swap{
count+=2; ++i; }
else if((str[i]=='{' && str[i+1]=='}') || (str[i]=='}' && str[i+1]=='{')) //can swap{
count+=2; ++i; }
else if((str[i]=='[' && str[i+1]==']') || (str[i]==']' && str[i+1]=='[')) //can swap count+=2; ++i; }
}
return count;
}
// Driven code
int main(){
char str[] = ")([]]((";
int length=7;
cout << maxBalancedStr(str,length);
return 0;
} आउटपुट
4