मान लीजिए हमारे पास एक स्ट्रिंग है, जिसमें खुलने और बंद होने वाले पैरेंथेसिस हैं। हमें वैध (वेल-फॉर्म्ड) पैरेंथेसिस की सबसे लंबी लंबाई ढूंढनी है। इसलिए यदि इनपुट "))(())())" जैसा है, तो परिणाम 6 होगा, क्योंकि वैध स्ट्रिंग "(())()" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक स्टैक बनाएं, और -1 डालें, ans := 0 सेट करें
i के लिए range 0 से स्टैक की लंबाई - 1 तक
यदि s[i] खुलने वाला पैरेंथेसिस है, तो i को स्टैक में डालें
अन्यथा
यदि स्टैक खाली नहीं है और स्टैक का शीर्ष -1 नहीं है और s[स्टैक शीर्ष] खुलने वाला पैरेंथेसिस है, तो
स्टैक से शीर्ष तत्व हटाएं
ans := ans और i - स्टैक शीर्ष का अधिकतम
अन्यथा 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