পাইথনে দেওয়া স্ট্রিং থেকে বৈধ প্যarethেসিসের দীর্ঘতম দৈর্ঘ্য নির্ণয়

ধরুন, s একটি স্ট্রিং যা শুধুমাত্র খোলা এবং বন্ধ প্যarethেসিস নিয়ে গঠিত। আমাদের কাজ হল সর্বোচ্চ দৈর্ঘ্যের বৈধ (সঠিকভাবে গঠিত) প্যarethেসিস উপস্ট্রিং এর দৈর্ঘ্য বের করা। উদাহরণস্বরূপ, ইনপুট "))(())())" হলে ফলাফল হবে ৬, কারণ বৈধ স্ট্রিং="(())()"।

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

• একটি স্ট্যাক তৈরি করুন এবং -1 দিয়ে শুরু করুন, ans := 0
• i = 0 থেকে len(s)-1 পর্যন্ত লুপ চালান:
  • যদি s[i] == '(' হয়, তবে i স্ট্যাকে পুশ করুন
  • অন্যথায়:
    • যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের শীর্ষ -1 না হয় এবং s[stack[-1]] == '(' হয়, তবে স্ট্যাক থেকে পপ করুন এবং ans := max(ans, i - stack[-1])
    • অন্যথায় i স্ট্যাকে পুশ করুন
• ans ফেরত দিন

উদাহরণ কোড

class Solution(object):
    def solve(self, s):
        stack = [-1]
        ans = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
                    stack.pop()
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

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

ইনপুট

"))(())())"

আউটপুট

6