পাইথন ব্যবহার করে একটি বন্ধনী স্ট্রিং ব্যালেন্স করার জন্য ন্যূনতম সন্নিবেশ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে '(' এবং ')' ওপেনিং এবং ক্লোজিং বন্ধনী সহ একটি স্ট্রিং s আছে। আমরা বলতে পারি একটি বন্ধনী স্ট্রিং ভারসাম্যপূর্ণ যখন −

যেকোন বাম বন্ধনী '(' একটি অনুরূপ দুটি পরপর ডান বন্ধনী আছে'))'।
একটি বাম বন্ধনী '(' অনুরূপ দুটি পরপর ডান বন্ধনীর আগে যেতে হবে '))'।

সুতরাং উদাহরণস্বরূপ, "())", "())(()))" ভারসাম্যপূর্ণ কিন্তু ")()", "()))" নয়। যদি আমাদের এই ধরনের স্ট্রিং থাকে, তাহলে স্ট্রিংকে সুষম করার জন্য আমাদের বন্ধনীর সংখ্যা (খোলা বা বন্ধ) গণনা করতে হবে।

সুতরাং, যদি ইনপুটটি s ="(())))))" এর মত হয়, তাহলে আউটপুট হবে 1 কারণ যদি আমরা এটিকে বিভক্ত করি তবে আমরা "(()))))" পেতে পারি, তাই আমাদের প্রয়োজন স্ট্রিংটি "( ()) ()) ))" ভারসাম্যপূর্ণ করার জন্য একটি বাম বন্ধনী।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

:=0, n :=s
এর আকার
ret :=0, i :=0
যখন আমি
- যদি s[i] '(' এর মত হয়, তাহলে
:=o + 1
- অন্যথায়,
  - যদি i + 1
    - o যদি 0 হয়, তাহলে
      - ret :=ret + 1
    - অন্যথায়,
:=o - 1
- i :=i + 1
- অন্যথায়,
  - ret :=ret + 1
  - o যদি 0 হয়, তাহলে
    - ret :=ret + 1
  - অন্যথায়,
:=o - 1
- i :=i + 1
রিটার্ন ret + 2 * o

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

def solve(s):
   o = 0
   n = len(s)
   ret = 0
   i = 0
   while i < n:
      if s[i] == '(':
         o += 1
      else:
         if i + 1 < n and s[i + 1] == ')':
            if not o:
               ret += 1
            else:
               o -= 1
               i += 1
         else:
            ret += 1
            if not o:
               ret += 1
            else:
               o -= 1
      i += 1
   return ret + 2 * o
s = "(())))))"
print(solve(s))

ইনপুট

"(())))))"