পাইথনে লংগেস্ট ভ্যালিড প্যারেনথেসিস

ধরুন একটি স্ট্রিং আছে যা ওপেনিং এবং ক্লোজিং প্যারেনথেসিস নিয়ে গঠিত। আমাদের লংগেস্ট ভ্যালিড (well-formed) প্যারেনথেসিসের দৈর্ঘ্য বের করতে হবে। যেমন "))(())())" ইনপুটের জন্য ফলাফল ৬, কারণ ভ্যালিড স্ট্রিং "(())()"।

সমাধানের ধাপগুলো −

• স্ট্যাক তৈরি করুন এবং -1 ঢুকান, ans := 0
• i = 0 থেকে len(s)-1 পর্যন্ত − যদি s[i] == '(' হলে stack.append(i); অন্যথায় − যদি stack খালি না থাকে এবং stack[-1] != -1 এবং s[stack[-1]] == '(' হলে stack.pop(); ans = max(ans, i - stack[-1]); অন্যথায় stack.append(i)
• ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

class Solution(object):
    def longestValidParentheses(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.longestValidParentheses("))(())())"))

ইনপুট

"))(())())"

আউটপুট

6