আমাদের একটি স্ট্রিং দেওয়া আছে যেটিতে শুধু (), {}, [] ক্যারেক্টার রয়েছে। লক্ষ্য হলো সংলগ্ন ক্যারেক্টার স্ব্যাপ করা বা ক্যারেক্টার রিমুভ করেই সর্বোচ্চ দৈর্ঘ্যের ব্যালেন্সড স্ট্রিং বানানো। বিপরীত ব্র্যাকেট যুগল (}{, )(, ][) স্ব্যাপ করা যায়, একই ব্র্যাকেট ({, )), ]) স্ব্যাপ করা যায় না। ম্যাচিং পেয়ার নাইলে রিমুভ করা যায়।
ইনপুট
str[]= "{{{}}{]]][()" length 12
আউটপুট
Maximum length of balances string: 8
ব্যাখ্যা: প্রথম দুটি { স্ব্যাপ হয় না, রিমুভ। পরের {} ব্যালেন্সড। }{ স্ব্যাপ হয়। ]] রিমুভ। ][ স্ব্যাপ হয়ে [] হয়। () ব্যালেন্সড। ফাইনাল স্ট্রিং: {}{}[]() দৈর্ঘ্য ৮।
ইনপুট
str[]= "(((((()" length 7
আউটপুট
str[]= "(((((()" length 7
ব্যাখ্যা: শুধু str[5] ও str[6] ব্যালেন্সড, বাকি রিমুভ। ফাইনাল স্ট্রিং () দৈর্ঘ্য ২।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- char str[] ও length ইনপুট।
- maxBalancedStr(char str[], int len) ফাংশন ম্যাক্স ব্যালেন্সড দৈর্ঘ্য রিটার্ন।
- count = 0। স্ট্রিং ট্র্যাভার্স করলে সংলগ্ন ক্যারেক্টার চেক: (), )(, {}, }{, [], ][ - যেসব ব্যালেন্সড বা স্ব্যাপ করে ব্যালেন্সড হয়, count += 2 এবং i++ (নেক্সট পেয়ার স্কিপ)।
- শেষে count রিটার্ন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int maxBalancedStr(char str[20], int len){
int count = 0;
for (int i = 0; i < len; i++) {
if((str[i]=='(' && str[i+1]==')') || (str[i]==')' && str[i+1]=='(')){
count += 2; ++i;
}
else if((str[i]=='{' && str[i+1]=='}') || (str[i]=='}' && str[i+1]=='{')){
count += 2; ++i;
}
else if((str[i]=='[' && str[i+1]==']') || (str[i]==']' && str[i+1]=='[')){
count += 2; ++i;
}
}
return count;
}
int main(){
char str[] = ")([]]((";
int length = 7;
cout << maxBalancedStr(str, length);
return 0;
}আউটপুট
4
