पायथन में दो वैध पैरेंथेसिस स्ट्रिंग्स की अधिकतम नेस्टिंग डेप्थ

मान लीजिए हमारे पास एक स्ट्रिंग है, वह स्ट्रिंग एक वैध पैरेंथेसिस स्ट्रिंग (VPS) है यदि और केवल यदि इसमें \"(\" और \")\" कैरेक्टर्स ही हैं, और यह इन गुणों को संतुष्ट करती है -

यह एक खाली स्ट्रिंग है, या
इसे AB के रूप में लिखा जा सकता है, जहां A और B VPS हैं, या
इसे (A) के रूप में लिखा जा सकता है, जहां A एक VPS है।

हम किसी भी VPS S की नेस्टिंग डेप्थ depth(S) को नीचे की तरह भी परिभाषित कर सकते हैं -

depth(\"\") = 0
depth(A + B) = depth(A), depth(B) का अधिकतम, जहां A और B VPS हैं
depth(\"(\" + A + \")\") = 1 + depth(A), जहां A एक VPS है।

यदि हमारे पास एक VPS seq है, हमें इसे दो डिसजॉइंट सबसीक्वेंस A और B में विभाजित करना है, जैसे कि A और B VPS हैं (और A की लंबाई + B की लंबाई = seq की लंबाई)। अब यदि हम ऐसा कोई A और B चुनते हैं कि max(depth(A), depth(B)) न्यूनतम संभव मान है। तब हमें एक आंसर ऐरे (seq की लंबाई का) ढूंढना है जो A और B के ऐसे चुनाव को एनकोड करता है: answer[i] = 0 यदि seq[i], A का हिस्सा है, अन्यथा answer[i] = 1।

इसलिए यदि इनपुट \"()(())()\" जैसा है, तो आउटपुट [1,1,1,0,1,0,1,1] होगा।

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

n := seq की लंबाई, res := लंबाई n का 0s का ऐरे
c1, c2 := 0, 0
i को 0 से n - 1 तक रेंज में
- यदि seq[i] = '('
  - यदि c1 < c2, तो c1 को 1 से बढ़ाएं, अन्यथा c2 को 1 से बढ़ाएं और res[i] := 1
- अन्यथा
  - यदि c1 > c2, तो c1 को 1 से घटाएं, अन्यथा c2 को 1 से घटाएं और res[i]:= 1
res लौटाएं

उदाहरण

class Solution(object):
    def maxDepthAfterSplit(self, seq):
        n = len(seq)
        res = [0] *n
        c1,c2= 0,0
        for i in range(n):
            if seq[i] == '(':
                if c1c2:
                    c1-=1
                else:
                    c2-=1
                    res[i]=1
        return res

ob = Solution()
print(ob.maxDepthAfterSplit(\"()(())()\"))

इनपुट

\"()(())()\"

आउटपुट

[1, 1, 1, 0, 1, 0, 1, 1]