पायथन में सबसे लंबे समय तक मान्य कोष्ठक

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

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

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

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

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

  • अन्यथा

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

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

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

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

• वापसी उत्तर

उदाहरण

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

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