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

मान लीजिए कि हमारे पास एक स्ट्रिंग s है। इसमें केवल कोष्ठक खोलना और बंद करना शामिल है। हमें सबसे लंबे समय तक वैध (अच्छी तरह से गठित) कोष्ठक की लंबाई का पता लगाना है। इसलिए यदि इनपुट "))(())())" जैसा है, तो परिणाम 6 होगा, क्योंकि वैध स्ट्रिंग "(())()" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक स्टैक बनाएं, और -1 डालें, उत्तर सेट करें:=0

• मैं के लिए 0 से लेकर ढेर की लंबाई तक - 1

  • अगर s[i] कोष्ठक खोल रहा है, तो i को स्टैक में डालें

  • अन्यथा

    • यदि स्टैक खाली नहीं है और स्टैक का शीर्ष -1 नहीं है और s[stack top] कोष्ठक खोल रहा है, तो

      • स्टैक से शीर्ष तत्व

      • उत्तर:=अधिकतम उत्तर और i - स्टैक टॉप

    • अन्यथा i को स्टैक में डालें

• वापसी उत्तर

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

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