পরবর্তির দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম যা স্টিল টি মুছে ফেলা যায় পাইথনে s-এর পরবর্তী অংশ

ধরুন আমাদের একটি স্ট্রিং s এবং আরেকটি স্ট্রিং টি আছে। এবং t হল s-এর একটি অনুগামী। আমাদের একটি সাবস্ট্রিং এর সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করতে হবে যা আমরা s থেকে মুছে ফেলতে পারি যাতে, t এখনও s-এর একটি অনুগামী।

সুতরাং, যদি ইনপুটটি s ="xyzxyxz" t ="yz" এর মত হয়, তাহলে আউটপুট হবে 4, যেহেতু আমরা সাবস্ট্রিং "abca" সরিয়ে দিতে পারি

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

বাম :=একটি নতুন তালিকা, ডানে :=এছাড়াও একটি নতুন তালিকা
c1 :=-1, c2 :=-1, c3 :=-1
j :=0
0 থেকে s আকারের রেঞ্জের জন্য, করুন
- যদি s[i] t[j] এর মত হয়, তাহলে
  - বাম প্রান্তে i সন্নিবেশ করুন
  - j :=j + 1
- যদি j টি আকারের সমান হয়, তাহলে
  - c1 :=s - i - 1
    এর আকার
  - লুপ থেকে বেরিয়ে আসুন
j :=t - 1
এর আকার
i এর জন্য s - 1 থেকে 0 এর রেঞ্জের আকার, 1 দ্বারা হ্রাস করুন, করুন
- যদি s[i] t[j] এর মত হয়, তাহলে
  - 0
    অবস্থানে ডানদিকে i সন্নিবেশ করুন
  - j :=j - 1
- যদি j -1 এর মত হয়, তাহলে
  - c2 :=i
  - লুপ থেকে বেরিয়ে আসুন
আমি 0 থেকে t - 1 এর আকারের মধ্যে, কর
- c3 :=সর্বাধিক c3 এবং (ডান[i + 1] - বাম[i] - 1)
সর্বাধিক c1, c2 এবং c3 ফেরত দিন

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

class Solution:
   def solve(self, s, t):
      left = []
      right = []
      c1 = -1
      c2 = -1
      c3 = -1
      j = 0
      for i in range(len(s)):
         if s[i] == t[j]:
            left.append(i)
            j += 1
         if j == len(t):
            c1 = len(s) - i - 1
            break
      j = len(t) - 1
      for i in range(len(s) - 1, -1, -1):
         if s[i] == t[j]:
            right.insert(0, i)
            j -= 1
         if j == -1:
            c2 = i
            break
      for i in range(len(t) - 1):
         c3 = max(c3, right[i + 1] - left[i] - 1)
      return max(c1, c2, c3)
ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

ইনপুট

"xyzxyxz", "yz"