পাইথনে প্যারেনথেসিস ভ্যালিড করতে মিনিমাম অ্যাড করুন

একটি স্ট্রিং S দেওয়া আছে যাতে শুধু '(' এবং ')' আছে। যেকোনো পজিশনে মিনিমাম সংখ্যক প্যারেনথেসিস অ্যাড করে স্ট্রিংটি ভ্যালিড করতে হবে। প্যারেনথেসিস স্ট্রিং ভ্যালিড হবে যদি:

• সেটি খালি স্ট্রিং হয়
• XY আকারে লেখা যায় (X এবং Y ভ্যালিড স্ট্রিং)
• (A) আকারে লেখা যায় (A ভ্যালিড স্ট্রিং)

স্ট্রিং "()))((" হলে ৪টি প্যারেনথেসিস অ্যাড করতে হবে।

সমাধানের ধাপসমূহ

• যদি S খালি হয়, 0 রিটার্ন
• count := 0, temp := খালি অ্যারে, temp_counter := 0
• S-এ প্রতিটি ক্যারেক্টার i-এর জন্য:
  • যদি i ওপেনিং প্যারেনথেসিস হয়, temp-এ অ্যাড করুন
  • অন্যথায়: যদি temp-র লাস্ট এলিমেন্ট ওপেনিং হয়, তবে সেটি পপ করুন, অন্যথায় i অ্যাড করুন
• temp-এর সাইজ রিটার্ন

উদাহরণ

class Solution:
    def minAddToMakeValid(self, S):
        if not S:
            return 0
        count = 0
        temp = []
        temp_counter = 0
        for i in S:
            if i == '(':
                temp.append(i)
            else:
                if len(temp) > 0 and temp[len(temp)-1] == '(':
                    temp.pop(len(temp)-1)
                else:
                    temp.append(i)
        return len(temp)

ob = Solution()
print(ob.minAddToMakeValid("()))(("))

ইনপুট

"()))(("

আউটপুট

4