পাইথনে প্রদত্ত স্ট্রিং থেকে দীর্ঘতম বৈধ বন্ধনীর দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা একটি স্ট্রিং s আছে. এটি শুধুমাত্র খোলা এবং বন্ধ বন্ধনী নিয়ে গঠিত। আমাদের দীর্ঘতম বৈধ (সুগঠিত) বন্ধনী সাবস্ট্রিং এর দৈর্ঘ্য খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি “))(())()”” এর মত হয়, তাহলে ফলাফল হবে 6, কারণ বৈধ স্ট্রিং হল “(())()”।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি স্ট্যাক তৈরি করুন এবং সন্নিবেশ করুন -1., উত্তর সেট করুন :=0

• 0 থেকে স্ট্যাকের দৈর্ঘ্য - 1

  এর মধ্যে i এর জন্য

  • যদি s[i] বন্ধনী খুলছে, তাহলে i ঢোকান স্ট্যাকের মধ্যে

  • অন্যথায়

    • যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের শীর্ষ -1 না হয় এবং s[স্ট্যাক টপ] বন্ধনী খুলছে, তাহলে

      • স্ট্যাক থেকে শীর্ষ উপাদান

      • উত্তর :=সর্বোচ্চ উত্তর এবং 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