ধরুন আমাদের n অক্ষর সহ একটি স্ট্রিং S আছে। S-এ ছোট হাতের ইংরেজি অক্ষর এবং ')' অক্ষর রয়েছে। স্ট্রিংটি খারাপ, যদি শেষে ')' অক্ষরের সংখ্যা অবশিষ্ট অক্ষরের সংখ্যার চেয়ে কঠোরভাবে বেশি হয়। আমাদের পরীক্ষা করতে হবে এস খারাপ কিনা।
সুতরাং, যদি ইনপুটটি S ="fega))))))" এর মত হয়, তাহলে আউটপুটটি সত্য হবে, কারণ এটি খারাপ কারণ এখানে 4টি অক্ষর এবং 6') রয়েছে৷
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
ans := 0 n := size of S i := n - 1 while (i >= 0 and S[i] is same as ')'), do: (decrease i by 1) z := n - 1 - i ans := 2 * z - n if ans > 0, then: return true Otherwise return false
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
bool solve(string S) {
int ans = 0;
int n = S.size();
int i = n - 1;
while (i >= 0 && S[i] == ')')
i--;
int z = n - 1 - i;
ans = 2 * z - n;
if (ans > 0)
return true;
else
return false;
}
int main() {
string S = "fega))))))";
cout << solve(S) << endl;
} ইনপুট
"fega))))))"
আউটপুট
1
