পাইথনে দুটি বৈধ প্যারেনথেসিস স্ট্রিং-এর সর্বোচ্চ নেস্টিং ডেপথ মিনিমাইজ করা

মনে করুন একটি স্ট্রিং আছে, যা ভ্যালিড প্যারেনথেসিস স্ট্রিং (VPS) যদি এবং কেবল যদি সেটি শুধু ( এবং ) ক্যারেক্টার দিয়ে গঠিত হয় এবং নিচের প্রপার্টিগুলো সন্তুষ্ট করে:

• খালি স্ট্রিং, অথবা

• AB হিসেবে লেখা যায়, যেখানে A এবং B VPS, অথবা

• (A) হিসেবে লেখা যায়, যেখানে A VPS।

নেস্টিং ডেপথ depth(S) নিচের মতো ডিফাইন করা হয়:

• depth("") = 0

• depth(A + B) = max(depth(A), depth(B)), যেখানে A এবং B VPS।

• depth("(" + A + ")") = 1 + depth(A), যেখানে A VPS।

আমাদের একটি VPS seq দেওয়া আছে, এটিকে দুটি ডিসজয়েন্ট সাবসিকোয়েন্স A এবং B-এ ভাগ করতে হবে, যাতে A এবং B VPS হয় (এবং len(A) + len(B) = len(seq))। এখন যেকোনো এমন A এবং B বেছে নিলে max(depth(A), depth(B)) ন্যূনতম হয়। আমাদের একটি আンサー অ্যারে (লেন্থ len(seq)) বের করতে হবে যা সেটি এনকোড করে: answer[i] = 0 যদি seq[i] A-এর অংশ, অন্যথায় 1।

ইনপুট যদি "()(())()" হয়, তবে আউটপুট হবে [1,1,1,0,1,0,1,1]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (লালচী পদ্ধতি / Greedy):

• n := len(seq), res := n সাইজের ০ দিয়ে পূরণ করা অ্যারে

• c1, c2 := 0, 0

• for i in range 0 to n-1:

  • যদি seq[i] == '(':

    • যদি c1 < c2, তবে c1++, অন্যথায় c2++ এবং res[i] := 1।

  • অন্যথায় (যদি ')'):

    • যদি c1 > c2, তবে c1--, অন্যথায় c2-- এবং res[i] := 1।

• return 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 c1 < c2:
                    c1 += 1
                else:
                    c2 += 1
                    res[i] = 1
            else:
                if c1 > c2:
                    c1 -= 1
                else:
                    c2 -= 1
                    res[i] = 1
        return res

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

ইনপুট

"()(())()"

আউটপুট

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