पायथन में दी गई स्ट्रिंग से सबसे लंबे वैध पैरेंथेसिस की लंबाई ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है। इसमें केवल खुलने और बंद होने वाले पैरेंथेसिस हैं। हमें सबसे लंबे वैध (वेल-फॉर्म्ड) पैरेंथेसिस सबस्ट्रिंग की लंबाई ज्ञात करनी है। उदाहरण के लिए, यदि इनपुट है "))(())())", तो परिणाम 6 होगा, क्योंकि वैध स्ट्रिंग "(())()" है।

एल्गोरिदम (स्टैक आधारित)

• स्टैक बनाएं और -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